[백준 15903번] 카드 합체 놀이(자바)

백준알고리즘 15903번 : 카드 합체 놀이

 

 

이 문제는 매회 숫자가 더 작은 카드를 골라서 덧셈하도록하여 카드들의 총합을 작게 만드는 것이 목표이다.
오름차순으로 정려한 뒤에, 최초 카드들중 가장 작은 숫자들끼리 더했을 때, 그 숫자가 새로운 작은 숫자일수도,

그렇지 않을 수도 있기 때문에
이를 비교하기위해 더해서 새롭게 생성된 숫자는 queue에 담아서 별도로 비교해주도록 하였다.

 

풀이 과정

---

1. 숫자를 배열에 담고 오름차순으로 정렬한다.
2. 카드 합체 횟수 M만큼 for문을 돌며, queue가 비어있거나 queue의 peek값이 배열의
    비교대상보다 크면 배열 card의 값을, 크지 않으면 queue의 poll값을 합체 대상으로 뽑는다.
3. 2번의 행위를 2번 반복하여 더 해진 값을 queue에 두 번 add한다.
4. 반복이 완료 된 후, queue값과 배열 값을 더하여 답을 출력한다.

 

 

▽ 정답 소스 보기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {// No15903 카드 합체 놀이

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

		String[] tmp = br.readLine().split(" ");

		int num = Integer.parseInt(tmp[0]);
		int sumCnt = Integer.parseInt(tmp[1]);

		long[] card = new long[num];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < num; i++) {
			card[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(card);
		Queue<Long> queue = new LinkedList<>();

		int pos = 0;
		for (int j = 0; j < sumCnt; j++) {
			long num1 = 0;
			long num2 = 0;
			if (queue.isEmpty() || (pos < card.length && queue.peek() >= card[pos])) {
				num1 = card[pos];
				pos++;
			} else {// 비어있지 않고, stack의 peek이 더 작을때
				num1 = queue.poll();
			}

			if (queue.isEmpty() || (pos < card.length && queue.peek() >= card[pos])) {
				num2 = card[pos];
				pos++;
			} else {// 비어있지 않고, stack의 peek이 더 작을때
				num2 = queue.poll();
			}

			queue.add(num1 + num2);
			queue.add(num1 + num2);

		}

		long sum = 0;

		while (pos < card.length) {
			sum += card[pos];
			pos++;
		}

		while (!queue.isEmpty()) {
			sum += queue.poll();

		}
		System.out.println(sum);

	}
}