[SWEA] 1860. 진기의 최고급 붕어빵

문제

진기는 붕어빵 가게를 운영하고 있다.

진기가 파는 붕어빵은 그냥 붕어빵이 아니라 겉은 바삭! 속은 말랑! 한입 물면 팥 앙금이 주르륵 흘러 입안에서 춤을 추며,

절로 어릴 적 호호 불며 먹었던 뜨거운 붕어빵의 추억이 떠올라 눈물이 나오게 되는 최고급 붕어빵이다.

진기는 이런 붕어빵을 보통 사람들에게는 팔지 않는다.

그는 무조건 예약제로만 손님을 받으며, 예약을 하려는 손님들은 진기의 까다로운 자격 검증에서 합격해야만 붕어빵을 맛 볼 자격을 얻는다.

그래서 오늘은 N명의 사람이 자격을 얻었다.

진기는 0초부터 붕어빵을 만들기 시작하며, M초의 시간을 들이면 K개의 붕어빵을 만들 수 있다.

서빙은 진기가 하는 것이 아니기 때문에, 붕어빵이 완성되면 어떤 시간 지연도 없이 다음 붕어빵 만들기를 시작할 수 있다.

0초 이후에 손님들이 언제 도착하는지 주어지면, 모든 손님들에게 기다리는 시간없이 붕어빵을 제공할 수 있는지 판별하는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 세 자연수 N, M, K(1 ≤ N, M, K ≤ 100)가 공백으로 구분되어 주어진다.

두 번째 줄에는 N개의 정수가 공백으로 구분되어 주어지며,

각 정수는 각 사람이 언제 도착하는지를 초 단위로 나타낸다. 각 수는 0이상 11,111이하이다.

출력

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

모든 손님에 대해 기다리는 시간이 없이 붕어빵을 제공할 수 있으면 “Possible”을, 아니라면 “Impossible”을 출력한다.

예제 입력

4
2 2 2
3 4
2 2 2
1 2
2 2 1
4 2
2 2 1
3 2

예제 출력

#1 Possible
#2 Impossible
#3 Possible
#4 Impossible

코드

package live13._02_진기의_최고급_붕어빵;

import java.util.*;
import java.io.*;

public class Solution {
	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("src/live13/_02_진기의_최고급_붕어빵/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken()); // N명의 사람
			int M = Integer.parseInt(st.nextToken()); // M초의 동안
			int K = Integer.parseInt(st.nextToken()); // K개의 붕어빵을 만들 수 있음

			int bungeobbangCnt = 0;
			int[] customerTime = new int[N];

			st = new StringTokenizer(br.readLine());
			// 손님 N명이 각각 도착하는 시간
			for (int i = 0; i < N; i++) {
				customerTime[i] = Integer.parseInt(st.nextToken());
			}

			// 시간순 정렬!
			Arrays.sort(customerTime);
			boolean canSell = true;
			for (int i = 0; i < N; i++) {
				if (customerTime[i] / M * K - i <= 0) {
					canSell = false;
					break;
				}
			}
			
			bw.write("#" + String.valueOf(tc) + " " + (canSell ? " Possible\n" : " Impossible\n"));
		}

		br.close();
		bw.close();
	}
}

풀이

💡Key Point

• 시간 기준이 아니라 도착했을 때 붕어빵이 남아있는지를 기준으로 풀어보도록 하죠.
• 손님이 도착한 시간에
  • 붕어빵이 몇 개 있어야하고,
  • 붕어빵이 없으면 못 팔고,
  • 이전 손님이 있었다면 -1개
  • 이전 손님 수에 따라 -1 * N이 되겠죠?

💡남아있는 붕어빵 개수 구하기

1. customerTime[i] / M
   • 진기는 M초 동안 K개의 붕어빵을 만듭니다.
   • 손님이 온 시간을 M으로 나누면 그동안 K개의 붕어빵을 몇 번만들었는지 알 수 있습니다.
   • 그 몇 번에 K를 곱하면 해당 시간에 붕어빵을 몇 개 만들었는지 알 수 있겠죠?
2. customerTime[i] / M * K
   • 이렇게 손님이 온 시간에 붕어빵을 몇 개 만들었는지 구합니다.
   • 근데 예를 들어서, 5번째 손님까지 각각 하나씩 먹었다면 -5를 해야겠죠?
   • 이는 해당 시간동안 손님이 몇 번 들어왔는지 빼면 됩니다.
3. customerTime[i] / M * K - i
   • for문은 들어온 손님 수만큼 순회합니다.
   • 그러면 -i를 하면 자연스럽게 손님들이 하나씩 붕어빵을 먹고가게 됩니다.
   • 여기까지가 손님이 방문했을 때 남은 붕어빵의 개수가 되는거에요.
4. customerTime[i] / M * K - i <= 0
   • 근데 도착했는데 붕어빵이 없다?
   • 그러면 false를 처리하는 거에요.
   • 그럴 일은 없어야겠지만, 음수가 나올 경우를 대비하여 <=를 사용했습니다.