진기의 최고급 붕어빵


SW Expert Academy 1860: 진기의 최고급 붕어빵

문제보기
Alt text

풀이

0초에 손님이 오면 붕어빵은 없기 때문에 무조건 불가능임을 주의
또한, 같은 시간에 여러 명의 손님이 올 수 있음을 주의

소스코드

import java.util.Arrays;
import java.util.Scanner;

public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			int N = sc.nextInt(); // N명의 손님
			int M = sc.nextInt(); // M초의 시간으로
			int K = sc.nextInt(); // K개의 붕어빵 만듦
			int[] client = new int[N]; // 손님이 몇초에 도착하는지 담을 배열
			for (int i = 0; i < N; i++) {
				client[i] = sc.nextInt();
			}

			int bread = 0; // 붕어빵의 개수

			// 손님 배열을 오름차순으로 정렬
			Arrays.sort(client);

			int second = 1; // 초(시간)
			int idx = 0; // 손님 배열의 인덱스
			boolean flag = true;

			if (client[0] == 0)	//0초에 손님이 오면 무조건 불가능
				flag = false;
			else {
				while (second <= client[N - 1]) { // 제일 마지막에 오는 손님의 시간까지 반복
					// M초의 시간마다 K개의 붕어빵이 만들어짐
					if (second % M == 0)
						bread += K;

					// 손님이 오면 붕어빵을 하나 준다
					if (second == client[idx]) { // 손님이 올 시간이 됨
						while (second == client[idx]) {	//같은 시간에 손님이 여러명 올 수 있으니 반복
							if (bread != 0) {
								bread = bread - 1; // 손님에게 붕어빵 하나를 줌
								idx++;
								if (idx >= N)
									break;
							} else { // 붕어빵이 없으면 불가능
								flag = false;
								break;
							}
						}
					}
					second++;
				}
			}

			if (flag)
				System.out.println("#" + tc + " " + "Possible");
			else
				System.out.println("#" + tc + " " + "Impossible");
		}
	}
}