BOJ_1715 : 카드 정렬하기

👉 문제링크

1715번: 카드 정렬하기

---

---

🔸 문제 분석 🔸

• 카드 묶음들을 합칠때 최소 비교 횟수를 출력한다.

🔸 문제 풀이 🔸

• 작은 묶음부터 합쳐야 최소값이 나오는걸 문제에서 확인할 수 있으므로,
  그리디 알고리즘으로 접근해 우선순위 큐를 이용하여 풀이한다.
• 두 최소값 원소를 뽑아 그 합을 정답에 누적하고, 다시 그 합을 우선순위 큐에 넣는다.
  • 우선순위 큐의 원소가 1개가 남을 때 까지 반복한다.
  • 합으로 만들어진 새 묶음이 기존 묶음보다 클 수 있음에 유의한다.

🔸 코드 🔸

import java.io.*;
import java.util.PriorityQueue;

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 answer = 0;
        int n1, n2;

        while (pq.size() > 1) {
            n1 = pq.poll();
            n2 = pq.poll();
            answer += n1 + n2;
            pq.add(n1 + n2);
        }

        bw.write(Integer.toString(answer));
        bw.flush();
    }
}

🔸 코드 해석 🔸

• N개의 묶음을 우선순위 큐 pq에 저장한다.
• pq의 크기가 1이 될 때까지, 원소를 2개씩 꺼내 그 합을 누적하고, 다시 pq에 넣는 것을 반복한다.
• 최종으로 누적된 answer의 값이 정답이다.

---

🔸 end 🔸

• 그리디적으로 접근해서 단순히 최소값만 누적하면 되는 줄 알았는데, 새로 만들어진 묶음의 크기가 기존 값보다 더 클 수 있기 때문에 다시 우선순위 큐에 넣어주어야 했다.
  • 이 부분을 구현하지 않아서 1회 틀렸다.