BOJ 1715 - 카드 정렬하기

문제

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

 

 

풀이

오름차순으로 정렬해서 더하면 되는 그리디 문제다

이때 주의할 점은 작은 수끼리 더한 값도 다시 리스트에 넣어서 오름차순으로 정렬해야 한다

우선순위 큐를 이용하면 최소값을 O(1) 시간 만에 찾을 수 있고, 오름차순으로 정렬하는 데 O(log n) 만큼 걸리므로 문제를 해결할 수 있다

 

 

코드

python

import sys
import heapq
 
heap = []
sum = 0
 
n = int(sys.stdin.readline())
 
for _ in range(n):
    card_size = int(sys.stdin.readline())
    heapq.heappush(heap, card_size)
 
while len(heap) > 1:
    a = heapq.heappop(heap)
    b = heapq.heappop(heap)
    sum += a + b
    heapq.heappush(heap, a + b)
 
print(sum)

 

 

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
 
public class Main {
 
    private static int n;
    private static PriorityQueue<Integer> pq = new PriorityQueue<>();
 
    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
 
    private static void solve() {
        int sum = 0;
        while (pq.size() != 1) {
            int a = pq.poll();
            int b = pq.poll();
            sum += a + b;
            pq.add(a + b);
        }
 
        System.out.println(sum);
    }
 
    private static void input() throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bufferedReader.readLine());
 
        for (int i = 0; i < n; i++) {
            pq.add(Integer.parseInt(bufferedReader.readLine()));
        }
    }
 
}