알고리즘/백준

[BJ] 1715 카드 정렬하기 Java

밥은답 2023. 1. 25. 18:18
반응형

백준 1715 카드 정렬하기 

문제

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

 

1715번: 카드 정렬하기

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장

www.acmicpc.net

 

아이디어

  • 문제의 예시에도 나와있듯이 최소한으로 비교하기 위해서는 가장 작은 값끼리 먼저 더해야한다
  • 즉 10, 20, 40이면 (10+20) + (30+40) 을 해야함
  • 계속해서 작은 값을 먼저 더해야되기 때문에 PriorityQueue 우선순위큐를 사용하면 된다

코드

package baekjoon;
import java.util.*;

class BJ1715 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        // 가장 낮은 숫자들을 먼저 더해야하기 때문에 우선순위 큐를 사용해서
        // 낮은값들을 먼저 뽑아서 더하는 방식으로 간다
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int i=0; i<n; i++) {
            int num = sc.nextInt();
            pq.offer(num); // 우선순위큐 이기 때문에 poll()할때 작은 값이 먼저 나옴
        }

        int answer = 0;

        // 큐에 숫자가 두개 있어야 더 할 수 있음
        while (pq.size() > 1) {
            int a = pq.poll();
            int b = pq.poll();
            answer += a+b;
            pq.offer(answer); // 더한값을 다시 넣어줘야 최대 횟수 가능
            // 10+20 = 30 했다면, 30 + 40 해야되기 때문에 30넣어줌
        }
        System.out.println(answer);
    }
}
반응형