다음 손님이 오는 시간을 enterTime, 그리고 가장 최근에 붕어빵을 구운 시간을 beforeTime이라고 하자.
그러면 진기가 다음 손님이 오기 전까지 붕어빵을 구울 수 있는 시간은 enterTime - beforeTime이다.
진기가 남아있는 시간 동안 구울 수 있는 붕어빵의 개수는 (enterTime - beforeTime) / M * K이다.
그리고 진기가 가장 최근에 붕어빵을 구운 시간은beforeTime + (newCnt / K * M)이다.
진기가 다음 손님이 오기 전까지 구울 수 있는 붕어빵의 수를 구해서 현재 가지고 있는 붕어빵의 총개수를 구한다. 만약 붕어빵의 개수가 0개이라면 다음 손님에게 팔 붕어빵이 없는 것이기 때문에 imPossible을 출력하고 1개 이상 있다면 Possible을 출력한다.
import java.util.*;
class Solution
{
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
StringBuffer sb = new StringBuffer();
int T = sc.nextInt();
for(int tc=1; tc<=T; tc++){
sb.append("#").append(tc).append(" ");
int N = sc.nextInt();
int M = sc.nextInt();
int K = sc.nextInt();
PriorityQueue<Integer> queue = new PriorityQueue<>();
for(int i=0; i<N; i++){
queue.add(sc.nextInt());
}
int cnt = 0; //현재 가지고 있는 붕어빵 갯수
int beforeTime = 0; //이전에 붕어빵 나온 시간
boolean isPossible = true; //구매 가능한지 확인
while(!queue.isEmpty()){
int enterTime = queue.poll(); //손님 도착 시간
int newCnt = (enterTime - beforeTime) / M * K; //남은 시간동안 만들수 있는 붕어빵 갯수
cnt += newCnt;
beforeTime = beforeTime + (newCnt / K * M);
if(cnt == 0){
isPossible = false;
break;
}
cnt -= 1;
}
if(isPossible)
sb.append("Possible").append("\n");
else
sb.append("Impossible").append("\n");
}
System.out.println(sb);
}
}