[백준] 13975 : - JAVA

🙋🏻‍♀️ 우선순위 큐 사용!

골드4라서 조금 어렵겠다 생각했는데, 아니다.
생각해보면, 파일은 무조건 2개씩 합쳐지기때문에 어떻게 합치든 횟수는 고정이다!
동일한 횟수에 최소비용을 구하려면, 각 횟수마다 합이 최소가 되도록하면된다.

따라서 우선순위 큐를 이용한다!

Troubleshooting

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

public class Main {
	
	static PriorityQueue<Integer> pq = new PriorityQueue<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for(int i=0; i<T; i++) {
			int answer = 0;
			pq.clear();
			int K = Integer.parseInt(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<K; j++) {
				pq.add(Integer.parseInt(st.nextToken()));
			}
			
			while(!pq.isEmpty()) {
				if(pq.size() == 1) { 
					break;
				}
				
				int sum = pq.poll() + pq.poll();
				answer += sum;
				pq.add(sum);
			}
			System.out.println(answer);
		}	
	}
}

문제

테케는 통과했는데, 틀렸습니다를 받았다.

원인

타입이 int인게 문제였다! 범위를 초과한다.

해결

int관련부분 long으로 수정

제출코드

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

public class Main {
	
	static PriorityQueue<Long> pq = new PriorityQueue<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for(int i=0; i<T; i++) {
			long answer = 0;
			pq.clear();
			int K = Integer.parseInt(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<K; j++) {
				pq.add(Long.parseLong(st.nextToken()));
			}
			
			while(!pq.isEmpty()) {
				if(pq.size() == 1) { 
					break;
				}
				
				long sum = pq.poll() + pq.poll();
				answer += sum;
				pq.add(sum);
			}
			System.out.println(answer);
		}	
	}
}

주의할 점

• 제발 코테풀 때, 타입주의하자!!!! Long 타입으로하자 왠만하면