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

🔗 문제 링크

13975번: 파일 합치기 3

---

⏳ 풀이

1. 우선순위큐에 파일의 크기를 넣어준다.

2. 큐에서 파일 2개를 꺼내 합한값을 비용에 더해주고 다시 큐에 넣어준다.

3. 큐에 원소가 1개 남으면 반복문을 종료해주고 비용을 리턴해준다.

---

💡 고찰

문제 지문과 정렬하고 싶게 주어진 입력을 보고 그리디 유형 문제일 것 같다고 생각했다. 가장 작은 값들을 먼저 더해서 큰값을 최소한으로 더하는 게 좋은 것 같아 우선순위큐로 오름차순으로 정렬을 해서 값을 구했더니 예제 출력과 동일하게 나왔다.

하지만 제출했는데 1%만에 “틀렸습니다.” 가 나왔다. 내가 푼 방법이 잘못됐나 고민하다가 지문을 보니 최대 출력값이 int 자료형으로는 턱없이 부족해 보였다. 자료형을 long으로 바꿔줘서 해결했다.

자료형 때문에 틀릴 때마다 “아 다음부터 이런 실수는 절대 안 해야지” 라고 생각하는데 그 생각이 흐릿해질 때마다 이렇게 나한테 경각심을 주는 것 같다. 실전에서 자료형 때문에 틀리면 얼마나 억울하리..

💻 소스코드

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

public class Main_bj_13975_파일합치기3 {

    public static void main(String[] args) throws Exception {

        System.setIn(new FileInputStream("res/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        for (int tc = 0; tc < T; tc++) {

            int N = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine(), " ");

            PriorityQueue<Long> pq = new PriorityQueue<>();
            for (int i = 0; i < N; i++) {
                pq.offer(Long.parseLong(st.nextToken()));
            }

            long answer = 0;

            while(true){

                if(pq.size() == 1) break;
                long num1 = pq.poll();
                long num2 = pq.poll();

                answer += num1+num2;
                pq.offer(num1 + num2);
            }
            System.out.println(answer);
        }
    }
}