백준 15903번 : 카드 합체 놀이 - 실버 1

✅ 문제

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

✅ 분류

• 그리디 알고리즘
• 우선순위큐 활용

✅ 공부한 내용

int vs long 범위 차이

int:  -2,147,483,648 ~ 2,147,483,647 (약 -21억 ~ 21억)
long: -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 (약 -922경 ~ 922경)

 

• 카드 개수 n: 최대 1,000개
• 초기 카드 값: 최대 1,000,000
• 합체 연산 m: 최대 15,000번

 

최종 result (모든 카드의 합)는:

• 최악의 경우 수십억, 수백억을 넘어감
• int 범위(21억)를 초과하면 오버플로우 발생
• 음수로 바뀌거나 이상한 값이 나옴
• 최악의 경우 = (최대 입력값) × (연산 횟수) × (카드 개수) → 이게 21억을 넘으면 long 사용!

문제 풀 때 팁

 

• 누적 합, 곱셈이 포함되면 long 의심
• "모든 원소의 합", "최댓값" 같은 키워드 주의
• 10^9 (10억) 이상의 수가 나오면 무조건 long

 

✅ 회고

읽자마자 이해하기 쉬운 문제였다. 다만 우선순위 큐 자료구조와 문법을 제대로 알고 있어야 한번에 풀린다.

그리고 자연수 1000000개 범위 때문에 처음에 int로 지정하고 풀었다가 터져서 long으로 수정하고 다시 푸니 해결되었다.

 

✅ 풀이

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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); 
        int m = Integer.parseInt(st.nextToken()); 

        st = new StringTokenizer(br.readLine());
        PriorityQueue<Long> pq = new PriorityQueue<>();

        for (int i = 0; i < n; i++) {
            long a = Integer.parseInt(st.nextToken());
            pq.add(a);
        }

        for (int j = 0; j < m; j++) {
            long b = pq.poll();
            long c = pq.poll();
            long sum = b + c;
            pq.add(sum);
            pq.add(sum);
        }

        long result = 0;
        for (long k : pq) {
            result += k;
        }

        System.out.println(result);

    }
}
// 주어진 데이터에서 가장 작은 수를 찾아서, 더한다음에 다시 넣어주기