진기의 최고급 붕어빵 (D3)

문제 링크

• 붕어빵이 먹고 싶어지는 문제 !
• 붕어빵은 M초에 K개씩 만들어지며, N명의 손님만이 맛을 볼 수 있다
• 하지만 이마저도 먹지 못할 수 도있는데 ! 그 이유는 붕어빵이 다 떨어졌을 때, 만들어지는 중이라도 지금 당장 만들어진 붕어빵이 없다면 판매할 수 없다고 판별
• 이 문제는 시간초를 기준으로 1초씩 증가시키는 방법과 M초씩 증가시키는 방법이 있다
  • 1초씩 증가시키는 방법은 해당시간이 M초로 나누어진다면 붕어빵을 K개 증가시키고, 해당시간에 손님이 왔으면 붕어빵을 줄 수 있는지 없는지 판별
  • M초씩 증가시키는 방법은 현재 시간에서 M초가 지나기전에 온 손님들이 있는지를 판별, 있다면 붕어빵을 줄 수 있는지 없는지 판별.
  • M초가 지나면 붕어빵 K개를 추가
• 처음엔 1초씩 증가시키는 방법으로 풀다가, 시간초과가 나올 것 같아서 M초씩 증가시키는 방법으로 풀었다

Solution

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

// 진기의 최고급 붕어빵
public class Solution {
	static int N, M, K;
	static int[] guest;

	static String isPossible() {
		int fishbread = 0; // 만들어진 붕어빵 수
		int idx = 0; // 손님 번호
		int time = 0;
		while (true) {
			while (time + M > guest[idx]) {
				if (fishbread-- == 0) {
					return "Impossible";
				}
				if (idx++ >= N - 1) {
					return "Possible";
				}
			}
			time += M;
			fishbread += K;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();

		for (int t = 1; t <= T; t++) {
			N = sc.nextInt(); // 손님 수
			M = sc.nextInt(); // M분마다
			K = sc.nextInt(); // K개 만든다
			guest = new int[N];
			for (int i = 0; i < N; i++) {
				guest[i] = sc.nextInt();
			}
			Arrays.sort(guest); // 손님이 도착한시간 빨리온순서로 정렬

			System.out.printf("#%d %s\n", t, isPossible());
		}

	}
}