[Baekjoon] 16206_롤케이크

Silver I

문제(출처: https://www.acmicpc.net/problem/16206)

---

< 롤케이크 >

 

문제 풀이 

 

길이가 10인 롤케이크 개수의 최댓값을 구하기 위해서는 롤케이크를 자르기 위해 다음과 같은 우선순위를 부여했다.

1) 10으로 나누어 떨어지는 값을 먼저 자르기

2) 10으로 나누어 떨어지는 수가 여러 개라면 작은 값을 먼저 자르기

 

이렇게 우선순위를 부여한 이유는 20과 30이 있을 때 20은 한 번 자르면 10을 2개 만들 수 있지만 30을 한 번 자르면 10을 1개 만들 수 있기 때문이다.

 

 my solution (Java)

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

public class _16206_ { // 롤케이크

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

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		int answer = 0;
		PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				if (o1 % 10 == o2 % 10) {
					return o1 / 10 - o2 / 10;
				}
				return o1 % 10 - o2 % 10;
			}
		});

		st = new StringTokenizer(bf.readLine());
		for (int i = 0; i < n; i++) {
			int num = Integer.parseInt(st.nextToken());
			if (num == 10) {
				answer += 1;
			} else if (num > 10) {
				queue.add(num);
			}
		}

		while (m > 0 && !queue.isEmpty()) {
			int num = queue.poll();

			num -= 10;
			answer += 1;
			m -= 1;
			if (num == 10) {
				answer += 1;
			} else if (num > 10) {
				queue.add(num);
			}
		}
		System.out.println(answer);
	}
}

변수)
n, m : 롤케이크 개수, 자를 수 있는 최대 횟수
answer : 길이가 10인 롤케이크 개수의 최댓값
queue : 우선순위 큐

 

롤케이크 개수, 자를 수 있는 최대 횟수를 입력받는다. 어떤 롤케이크를 먼저 자를 것인지 우선순위 큐를 통해 우선순위를 정한다. 10으로 나누어 떨어지는 롤케이크를 먼저 자르되, 10으로 나누어 떨어지는 롤케이크가 여러 개라면 작은 값부터 자른다. n개의 롤케이크를 입력받으면서 길이가 10이면 answer+1, 10보다 크면 우선순위 큐에 저장한다. 10보다 작으면 답과 상관없이 때문이다. 

 

자를 수 있는 최대 횟수인 m이 0보다 크고 우선순위 큐가 비어있지 않다면 다음 과정을 반복한다.

1) queue poll

2) 롤케이크를 10만큼 자르고 answer+1, 자를 수 있는 최대 횟수-1

3) 자르고 남은 롤케이크의 길이가 10이라면 answer+1, 자르고 남은 롤케이크의 길이가 10보다 크다면 queue에 저장

 

길이가 10인 롤케이크 개수의 최댓값 출력

---

---