[BOJ] 15903 카드 합체 놀이 (Java)

문제 링크

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

 

 

문제 풀이

1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)
2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다.

다음 조건을 만족해야한다.

최소 값을 두 장 더하고 이 값으로 갱신해주고, 다시 최소 값 2장을 2장으로 갱신한다는 것을 파악하자마자

우선순위큐를 활용하는 문제라고 생각했다.

일단, sort 가 반복문마다 적용되야 하는 조건이였고, 이는 최소 힙으로 맨 앞 2값씩 뽑으면 최소 값을 빠르게 갱신할 것 이라고 생각했다.

그래서 PQ로 금방 접근했지만, 틀렸습니다가 나와서 당황 ㅎㅎ

 

카드의 개수 n (2<= n<=1000)이므로 1000장의 카드가 있을 수 있다.

카드에 쓰여진 자연수 (1<=ai<=1,000,000)  : 카드는 최대 백만이 쓰일 수 있다.

카드 합체 시 m(0<=m<=15 * n)이므로 15 * 1000번 합체할 수 있다.

 

모든 카드의 최대 값인 1,000,000이 쓰여있다고 쳤을 때, 2번 합체하면 2,000,000으로 증가하고, 

이런 값이 15000번 이상 반복되면 21억은 충분히 뛰어넘을 수 있다.

 

int 형에서 오버플로가 발생할 수 있으니 Long 타입이 필요하다!

시험 문제에서 만났으면 맞왜틀??하면서 당황했을 것 같다ㅎㅎ

 

코드

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/**
 * BOJ_15903_카드합체놀이
 *
 * 아기 : 자연수 n장
 * x번 카드 y 번 카드 골라 두 더한값
 * x번 카드와 y번 카드에 모두 덮어씀
 * m번 하면 끝남
 * */
public class BOJ_15903_카드합체놀이 {

    static BufferedReader br;
    static StringTokenizer st;

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

        br = new BufferedReader(new InputStreamReader(System.in));

        st = new StringTokenizer(br.readLine().trim());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        PriorityQueue<Long> queue = new PriorityQueue();
        st = new StringTokenizer(br.readLine().trim());
        for (int idx = 0; idx < N; idx ++) {
            queue.add(Long.parseLong(st.nextToken()));
        }

        for (int idx = 0; idx < M; idx ++) {
            long a = queue.poll();
            long b = queue.poll();
            long tmp = a + b;
            queue.add(tmp);
            queue.add(tmp);
        }

        long result = 0;
        while(!queue.isEmpty()) {
            result += queue.poll();
        }

        System.out.println(result);
    }
}