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

문제

 

 

접근 방식

맨 처음에 문제를 풀 때는 잘못 이해해서 정렬을 사용해서 풀 수도 있을 줄 알았는데

문제를 제대로 이해하고 보니 중간중간 계산 결과를 다시 넣을 때마다

정렬을 한다면 매우 비효율적이기 때문에 우선순위 큐를 사용해서 풀었다.

10 // 10개의 수가 주어졌을 때
123
456
234
998
12
7
876
887
455
234

 

만약 위와 같은 입력이 주어졌을 때 계산 순서는 다음과 같다.

7 + 12 = 19
19 + 123 = 142
142 + 234 = 376
376 + 234 = 610
610 + 455 = 1065
1065 + 456 = 1521
1521 + 876 = 2397
2397 + 887 = 3284
3284 + 998 = 4282

 

위 순서대로 계산하여 결과를 모두 더하면 13696이라는 답이 나오는데

이는 잘못된 풀이다.

7 + 12 = 19
19 + 123 = 142
142 + 234 = 376
234 + 376 = 610
455 + 456 = 911
610 + 876 = 1486
887 + 911 = 1798
998 + 1486 = 2484
1798 + 2484 = 4282

 

위와 같이 계산해서 결과를 모두 더했을 때 12108이라는 답이 나와야 정답이다.

 

처음 입력 받은 것을 정렬된 상태로 그대로 더하기만 해서 되는 문제가 아니라

두 카드 묶음을 더할 때마다 생기는 하나의 카드 묶음을 포함해서

다시 정렬된 상태로 계산해야 하기 때문이다.

 

이런 문제 때문에 처음 언급했던 것처럼 매번 정렬을 할 수도 없기 때문에

우선순위 큐를 사용해서 풀면 효율적인 것이다.

 

최소 힙의 규칙을 통해 항상 오름차순으로 우선순위 큐에서 값을 넣고 꺼낼 수 있기 때문에

두 카드 묶음을 합치고 합친 값을 다시 큐에 넣고 이를 반복하기만 하면

매번 정렬을 할 필요 없이 효율적으로 계산할 수 있다.

 

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		int sum = 0;
		int min = 0;

		PriorityQueue<Integer> pq = new PriorityQueue<>();

		for (int i = 0; i < n; i++) pq.offer(Integer.parseInt(br.readLine()));

		while (!pq.isEmpty()) {
			if (sum == 0) sum = pq.poll();
			else {
				sum += pq.poll();
				pq.offer(sum);
				min += sum;
				sum = 0;
			}
		}

		System.out.println(min);
	}
}