[백준] 13975 : 파일 합치기 3 (JAVA)

난이도

🥇 4

 

링크

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

13975번: 파일 합치기 3

---

문제

---

풀이과정

해당 문제는 그리디를 사용하는 문제이다.

 

생각해보면 굉장히 쉽게 풀 수 있는 문제여서 문제 설명에 쓰여진 예시를 보지 않는게 더 도움이 될 거 같다..

예시 설명에서는 [40 30 30 50] 이라는 값이 있을 때 

1) 먼저 40 + 30 = 70

2) 30 + 50 = 80

3) 70 + 80 = 150

이러한 과정으로 결과값을 출력하도록 설명하였는데 이렇게 하면 규칙을 찾기 힘들다.

 

처음에도 이러한 형식으로 풀어야 되는 줄 알고 정렬 후 (처음 값 + 마지막 값), (2번째 값 + N-1 값) + ...

이렇게 생각했었지만 전혀 아니었다!

 

 

해당 문제는 [40 30 30 50] 이라는 값이 있을 때

1) 먼저 [30 30 40 50] 으로 오름차순 정렬한 후

2) 30 + 30 = 60 생성

3) [40 50 60] 으로 오름차순 정렬한 후

4) 40 + 50 = 90 생성

5) [60 90] 으로 오름차순 정렬한 후

6) 60 + 90 = 150 생성

7) 60 + 90 + 150 = 300

이러한 과정으로 결과값을 출력하면 되는 것이다!

 

결국  (가장 작은 값 + 2번째로 작은 값) 을 한 값을 다시 넣어 최종적인 결과값을 구하면 된다.

새로운 값을 넣었을 때 계속 오름차순 정렬을 해야하기 때문에 우선순위 큐를 사용하였다.

 

🚨 소설을 구성하는 장의 수가 굉장히 커질 수 있기 때문에 int가 아닌 long을 써야한다..!

🚨 처음에 우선순위 큐에 계속 total 값을 넣는 실수를 했으니 이것도 주의하기..!

       (우선순위 큐에는 가장 작은 값과 2번째로 작은 값을 더한 결과값을 넣는 것이지 최종 값을 넣으면 안됨!)

---

전체 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            int K = Integer.parseInt(br.readLine());

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

            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < K; j++) {
                pq.offer(Long.parseLong(st.nextToken()));
            }

            long sum = 0;
            long total = 0;

            while (true) {
                long num1 = pq.poll();
                long num2 = pq.poll();

                sum = (num1 + num2);

                total += sum;

                if (pq.isEmpty()) {
                    break;
                }

                pq.offer(sum);
            }

            sb.append(total).append("\n");
        }

        System.out.print(sb);
    }
}

 

결과