[백준 11399] - ATM

문제

• 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다.
• 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 \(P_{i}\)분이다.
• 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다.
  • 예를 들어, 총 5명이 있고, \(P_{1}\) = 3, \(P_{2}\) = 1, \(P_{3}\) = 4, \(P_{4}\) = 3, \(P_{5}\) = 2 인 경우를 생각해보자.
  • [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다.
  • 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3 + 1 = 4분이 걸리게 된다.
  • 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3 + 1 + 4 = 8분이 필요하게 된다.
  • 4번 사람은 3 + 1 + 4 + 3 = 11분, 5번 사람은 3 + 1 + 4 + 3 + 2 = 13분이 걸리게 된다.
  • 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3 + 4 + 8 + 11 + 13 = 39분이 된다.
  • 줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1 + 2 = 3분, 1번 사람은 1 + 2 + 3 = 6분, 4번 사람은 1 + 2 + 3 + 3 = 9분, 3번 사람은 1 + 2 + 3 + 3 + 4 = 13분이 걸리게 된다.
  • 각 사람이 돈을 인출하는데 필요한 시간의 합은 1 + 3 + 6 + 9 + 13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.
• 줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 \(P_{i}\)가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

• 첫째 줄에 사람의 수 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 \(P_{i}\)가 주어진다. (1 ≤ \(P_{i}\) ≤ 1,000)

 

출력

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

 

솔루션

• 최소 시간을 구하는 문제인데, 규칙을 하나 찾을 수 있다.
  • 가장 적게 걸리는 시간은 총 인원 수만큼 더해지고, 그 다음 적게 걸리는 시간은 총 인원 수 - 1 만큼 더해진다.
  • 따라서, 시간을 오름차순 정렬한 뒤, 인원 수를 하나씩 감소시킨 값을 곱한 후에 나오는 값을 모두 더해주면 된다.

 

Code

import java.util.*;
import java.io.*;
 
public class Solution_11399 {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int N = Integer.parseInt(br.readLine());
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        PriorityQueue<Person> pq = new PriorityQueue<>();
 
        for (int i = 0; i < N; i++)
            pq.offer(new Person(i, Integer.parseInt(st.nextToken())));
 
        int result = 0;
 
        while (!pq.isEmpty()) {
            Person temp = pq.poll();
            
            result += (N--) * temp.time; // 핵심 솔루션 코드
        }
        
        bw.write(result + " ");
        bw.flush();
        bw.close();
        br.close();
    }
 
    public static class Person implements Comparable<Person> {
        int idx, time;
 
        public Person(int idx, int time) {
            this.idx = idx;
            this.time = time;
        }
 
        @Override
        public int compareTo(Person p) {
            if (this.time < p.time)
                return -1;
            else if (this.time == p.time) {
                if (this.idx < p.idx)
                    return -1;
            }
            return 1;
        }
    }
}
 

 

결과

5
3 1 4 3 2
32