[BOJ] 백준 15903번: 카드 합체 놀이(Java)

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

15903번: 카드 합체 놀이

 

문제

 

입력

첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다.

두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, a2, …, an이 공백으로 구분되어 주어진다. (1 ≤ ai ≤ 1,000,000)

 

출력

첫 번째 줄에 만들 수 있는 가장 작은 점수를 출력한다.

 

난이도

실버 5

 

Sol 1

배열을 정렬한 뒤 최솟값 두 개를 더한 값을 반영하는 과정을 m번 반복한다. 모두 반복한 후 배열에 저장된 모든 값을 더한다. 

직관적이고 간단한 로직이지만 매번 배열을 정렬해야 해서 시간이 오래 걸린다..

public class B15903_카드합체놀이 {
    static int n, m;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(bf.readLine());

        n = Integer.parseInt(token.nextToken());
        m = Integer.parseInt(token.nextToken());

        long[] cards = new long[n];

        token = new StringTokenizer(bf.readLine());

        for(int i=0; i<n; i++){
            cards[i] = Integer.parseInt(token.nextToken());
        }

        for(int i=0; i<m; i++){
            Arrays.sort(cards);
            long add = cards[0] + cards[1];
            cards[0] = add;
            cards[1] = add;
        }

        long sum = 0;
        for(long i : cards){
            sum += i;
        }

        System.out.println(sum);
    }
}

 

Sol 2

우선순위 큐를 사용해 풀 수 있다. 낮은 수가 우선순위를 가지는 큐를 사용하면 큐에 수를 add할 때마다 오름차순으로 정렬되어 들어가기 때문에 별도의 정렬 과정 없이도 최솟값을 바로 뽑아낼 수 있어 Sol 1에 비해 시간이 단축된다.

public class B15903_카드합체놀이 {
    static int n, m;
    static long sum = 0;
    static PriorityQueue<Long> input;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(bf.readLine());

        n = Integer.parseInt(token.nextToken());
        m = Integer.parseInt(token.nextToken());

        input = new PriorityQueue<>();

        token = new StringTokenizer(bf.readLine());

        for(int i=0; i<n; i++){
            input.add(Long.parseLong(token.nextToken()));
        }
        // input

        long x = 0, y = 0;

        for(int i=0; i<m; i++){
            if(!input.isEmpty()) x = input.poll();
            if(!input.isEmpty()) y = input.poll();

            long add = x + y;
            input.add(add);
            input.add(add);
        }

        sum = 0;
        while(!input.isEmpty()){
            sum += input.poll();
        }
        // operation

        System.out.println(sum);
        // output
    }
}

 

😅

카드에 적힌 각 자연수들의 최댓값이 1,000,000이기 때문에 배열과 변수의 타입을 long으로 선언해야 하지만, int로 선언해 틀렸다.