[백준] 11399번: ATM - JAVA

🔗 문제 링크

BOJ 11399번: ATM

11399번: ATM

 

📝 풀이 과정

사람들이 번호 순서대로 줄을 선 상태이고, [3, 1, 4, 3, 2]의 인출시간이 걸린다고 했을 때, 아래만큼의 시간이 각각 소요되게 된다.

0번 : 3				= 3
1번 : 3 + 1			= 4
2번 : 3 + 1 + 4			= 8
3번 : 3 + 1 + 4 + 3		= 11
4번 : 3 + 1 + 4 + 3 + 2		= 13
--------------------------------------
총 인출 시간 : 3 + 4 + 8 + 11 + 13 = 39

자세히 살펴보면, i번째 사람의 인출하는데 걸리는 시간은 0 ~ i번까지의 사람의 인출 시간의 합이다. 따라서, 인출 시간이 적은 사람이 앞에 서야(오름차순) 총 인출 시간이 감소하게 된다는 것을 알 수 있다.

 

다시 한번 예제를 보면, 0번째 선 사람의 인출 시간은 5번 등장하고, 1번째 사람의 인출 시간은 4번, ..., 4번째 사람은 1번 들어가는 것을 알 수 있다.

이를 통해, i번째 선 사람의 인출 시간은 (n - i)번 계산됨을 알 수 있다. 따라서 sum += p[i] * (n - i)을 통해 계산할 수 있게된다.

 

💻 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] p = new int[n];
        for (int i = 0; i < n; i++)
            p[i] = sc.nextInt();

        Arrays.sort(p);

        int sum = 0;
        for (int i = 0; i < n; i++)
            sum += p[i] * (n - i);

        System.out.println(sum);
    }
}

 

📊 제출 결과