[JAVA] 백준 1715 - 카드 정렬하기

백준 1715 - 카드 정렬하기

문제

---

알고리즘 (접근방법)

처음에는 배열을 사용하여 카드 묶음의 개수가 2로 나누어 떨어질때와 카드 묶음의 개수가 하나인 상황을 생각하였다.

정렬된 두 묶음 이라고 생각해서 입력 값이 정렬된 값이 들어오는 줄 알았다.

카드 묶음의 개수가 1개일때는 비교 대상이 없으므로 0 이라고 두었고,
카드 묶음의 개수가 존재할때에는 맨 처음 인덱스와 그 다음 인덱스를 더한 값이 최소값이 되는줄 생각했다. 물론 틀린 생각이였다.

제대로 된 접근 방법은 우선순위 큐를 사용하여 하나씩 빼 낸 후 두개의 빼내어진 수의 합을 다시 우선순위 큐에 넣고 더해주어야 한다.

배열만 생각하여 풀려고 했으나 전혀 풀이 방법이 안떠올랐다.

---

코드

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());

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

        for(int i = 0; i < n; i++) {
            pq.offer(Long.parseLong(br.readLine()));
        }

        long res = 0;
        while(pq.size() > 1) {
            long a = pq.poll();
            long b = pq.poll();

            res += a + b;
            pq.add(a + b);
        }

        System.out.println(res);
    }
}