개요

문제링크

직관적으로 생각하자!

문제분석

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

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

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

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

N명의 손님이 올 것이고, 해당 손님들은 적힌 숫자의 시간에 도착 할 것이다.

진기는 0초부터 붕어빵을 만들며, M초의 시간에 K개씩 만들어낼 수 있다.

이 대목을 생각하면 다음과 같은 공식을 생각할 수 있다.

T를 시간이라고 할때, T초에 진기가 만들어낼 수 있는 붕어빵의 개수를 구해보자.

T초에 진기가 만들어낼 수 있는 붕어빵의 개수 = ( T / M ) * K

예를 들어보자

3초에 손님이 도착하고 진기는 2초에 2개씩 만들어낼 수 있다.

진기는 0 , 1 초 동안 2개를 만들고 2초 손님부터 2개의 붕어빵을 팔 수 있다.

0 , 1 -> 2
2 , 3 -> 4

3초에 손님이 도착할때에는 2개의 붕어빵이 있다.

( 3 / 2 ) 2 = 1 2 = 2 개

그러면 여기서 좀 더 나아가서 생각해보자.

한명의 손님은 하나의 붕어빵만을 주문한다. 그렇게 되면, 현재 도착한 손님의 배열을 이용한다고 가정할때,우리는 그 손님이 오면 현재 남아있는 잔여 붕어빵 개수를 세어주어야 한다.
손님 하나가, 인덱스 + 1 이다 (인덱스는 항상 0 부터 시작하기 때문이다)

잔여 붕어빵 = 현재까지 만들어낸 붕어빵 - 현재 인덱스 수 + 1

손님이 왔을때, 잔여 붕어빵이 0보다 작다면, 현재 도착한 손님에게 붕어빵을 제공할 수 없다는 소리이다.

이제 이걸 코드로 보자

문제풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

/**
 * @author onyoo
 * @performance
 * @category
 * @note
 * @see
 * @since 11/28/23
 **/
public class Solution {
	static int T,N,M,K;
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		T = Integer.parseInt(br.readLine());
		for(int t=1;t<T+1;t++) {
			st = new StringTokenizer(br.readLine(), " ");

			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());

			int[] people = new int[N];

			st = new StringTokenizer(br.readLine(), " ");
			for(int i=0;i<N;i++) people[i] = Integer.parseInt(st.nextToken());

			Arrays.sort(people);

			String answer = "Possible";
			for(int i=0;i<people.length;i++){
				int bread = (people[i]/ M) * K - (i+1); // 잔여 붕어빵 개수
				if(bread < 0){
					answer = "Impossible";
					break;
				}
			}
			System.out.printf("#%d %s\n",t,answer);
		}
	}
}