백준 15903 카드 합체 놀이

15903번: 카드 합체 놀이

사용한 숫자로 다시 새로운 숫자를 만들어 사용해야 하고, 카드의 구성이 지속적으로 바뀌기 때문에 우선순위 큐를 사용해서 가장 작은 카드 두장을 계속 합해가면 풀 수 있습니다.

 

문제코드

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

public class boj15903_2 {
    public long solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer infoToken = new StringTokenizer(br.readLine());
        int cardCount = Integer.parseInt(infoToken.nextToken());
        int actions = Integer.parseInt(infoToken.nextToken());

        StringTokenizer cardToken = new StringTokenizer(br.readLine());
        PriorityQueue<Long> smallestCards = new PriorityQueue<>();
        for (int i = 0; i < cardCount; i++) {
            smallestCards.offer(Long.parseLong(cardToken.nextToken()));
        }
        // 두개의 숫자를 뽑아서 합한 뒤
        // 다시 우선순위 큐에 두번 넣어준다.
        for (int i = 0; i < actions; i++) {
            long first = smallestCards.poll();
            long second = smallestCards.poll();
            smallestCards.offer(first+second);
            smallestCards.offer(first+second);

        }
        // 정답을 구한다.
        long answer = 0;
        while (!smallestCards.isEmpty()){
            answer += smallestCards.poll();
        }

        return answer;
    }

    public static void main(String[] args) throws IOException {
        System.out.println(new boj15903_2().solution());
    }
}

결과

입력
4 2
4 2 3 1
출력
19