[ 백준 1715번 ] 카드 정렬하기

1. 문제

 

1715번: 카드 정렬하기

 

2. 풀이

입력으로 제공된 카드들의 누적합을 최소로 만드는 경우의 수를 만들라는 문제다. 이는 Greedy로 접근이 가능한데 이유는 아래와 같다.

 

a, b, c, d 총 네 개의 카드 묶음(a < b < c < d)이 있다고 가정해보자. 이 때, 먼저 만든 묶음은 또 다른 카드 묶음과 합쳐져야 하므로 한 번 더 더해져야 함을 의미한다. 즉, 더 큰 카드 묶음을 이용하여 새로운 묶음을 만들수록 큰 수가 중복해서 더해진다는 것을 의미한다. 굳이 큰 묶음인 d를 먼저 비교하여 큰 덩어리의 묶음을 만들어 놓을 이유가 없다는 것이다.

 

그렇다면 우리는 최대한 작은 묶음들을 다시 합치는 작업들을 진행해야 하고, 이를 위해서는 우선순위 큐(Priority Queue)가 필요함을 알 수 있다.

 

N개의 묶음이 있을 때, 이를 하나의 묶음으로 만들기 위한 비교연산은 총 (N - 1) 번의 연산이 필요하고, 이를 유념하여 우선순위 큐에 만들어진 새로운 묶음들을 넣으며 작업하면 해결할 수 있다.

 

3. 소스코드

public class Main {

    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());
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            pq.add(Integer.parseInt(br.readLine()));
        }

        int cnt = 0;
        int tot = 0;
        while (!pq.isEmpty()) {
            if (cnt == N - 1) break;
            int a = pq.poll();
            int b = pq.poll();

            tot += (a + b);
            pq.add(a + b);
            cnt++;
        }

        bw.write(tot + "");
        br.close();
        bw.close();
    }
}

 

GitHub - kwanik-kor/BOJ: Baekjoon Online Judge - explanation of solved problems and complete code