[Java] 백준 1715 카드 정렬하기 - 골드4

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;


public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int cnt = Integer.parseInt(br.readLine());

    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int i=0; i<cnt; i++)
      minHeap.add(Integer.parseInt(br.readLine()));

    int sum = 0;

    while(minHeap.size() != 1) {
      int a = minHeap.poll();
      int b = minHeap.poll();

//      if (a == 1 || b == 1) {
//        sum += Math.max(a, b);
//      } else {
        sum += (a+b);
//      }

      minHeap.add(a+b);
    }

    System.out.println(sum);
  }
}

• 주석을 처리한 코드를 제출해야 맞다고 나온다. 하지만 주석을 풀어야 맞는 답이 나온다고 생각한다. (문의는 넣어 둔 상태이다)
• 힙의 size가 1이 될 때(카드묶음 수가 1일 때)까지 반복한다
  • 힙에서 최솟값을 2개 뽑는다
  • 최솟값을 정렬하기 위해 필요한 비교횟수를 계산하여 sum에 더한다
  • 최솟값 2개를 더하여 다시 힙에 넣다

 

 

 

주석을 풀어야한다고 생각하는 이유

• 정렬된 카드 2장과 그냥 카드 1장이 있을 때, 2장과 1장을 섞어 정렬된 카드 3장을 만들어야할 경우 필요한 최소 비교횟수는 2이다
• 하지만 맞았다고 나온 코드는 정렬된 카드 2장과 그냥 카드 1장을 비교하는 최소 횟수를 3으로 처리해야 맞다고 나온다
• 예시 입력값은 다음과 같다

2
1
2

• 여기서 답이 2가 나와야 정상이라고 생각하지만, 3이라고 출력해야 맞다고 나온다.
• 문의를 넣어둔 상태이다