[그리디] 백준 ATM 11399번

[그리디]백준 ATM 11399번

---

문제 설명

ATM 1대에 N명의 사람이 줄을 서 있다.사람은 1번부터 N번까지 번호가 있고,i번 사람이 돈을 인출하는 데 걸리는 시간은 Pi분이다.

사람들이 줄을 서는 서는 순서에 따라 

돈을 인출하는데 필요한 시간의 합이 달라지게 된다.

각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하라.

 

입력

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

---

출력

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

 

** 풀이 방법

 

사람 수 N을 입력받는다.

N 크기의 A 배열을 생성해서

각 사람이 걸리는 시간을 입력 받는다.

Scanner sc = new Scanner(System.in);
        
int N = sc.nextInt();
int[] A = new int[N];
for (int i=0; i<N; i++) {
    A[i] = sc.nextInt();
}

 

A 배열을 오름차순으로 정렬하면최소값을 빠르게 구할 수 있다.최소값을 구할 count를 A[0]로 초기화한다.정렬 후 이중 for문을 돌려서첫 인덱스 ~ i번 인덱스까지의 합을 누적시킨다.for문 종료 후 count를 출력한다.

Arrays.sort(A);
     
int count = A[0];
for (int i=0; i<N-1; i++) {
    for (int j=0; j<=i+1; j++)
        count += A[j];
}
System.out.println(count);

 

 

<> 전체 코드 </>

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int[] A = new int[N];
        for (int i=0; i<N; i++) {
            A[i] = sc.nextInt();
        }
        Arrays.sort(A);
     
        int count = A[0];
        for (int i=0; i<N-1; i++) {
            for (int j=0; j<=i+1; j++)
                count += A[j];
        }
        System.out.println(count);
    }
}