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

문제

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

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

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

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

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

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

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

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

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

 

풀이방법

N, M, K와 N개의 정수 a[n]이 입력으로 주어졌을 때, 

 

1) 입력된 a[n]을 오름차순으로 정렬한다. 여담이지만 풀이 중 입력된 a[n]이 손님이 도착하는 시간의 간격인줄 알았지만 a[n]은 손님이 도착하는 시간이다.

 

2) a[n] 초에 진기가 만든 붕어빵의 개수를 구한다. K * (a[i] / m)

 

3) a[n] 초에 만든 붕어빵의 개수가 a[n]초까지 도착한 손님 수보다 작은지 확인한다.

 

4) 만약 만족하지 않는 다면 impossible

 

소스코드

package samsung;

import java.util.*;

public class s_1860 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			int k = sc.nextInt();
			ArrayList <Integer> a = new ArrayList<>();
			int flag = 0;
			
			for(int i = 0; i < n; i++) {
				int tmp = sc.nextInt();
				a.add(tmp);
			}
			
			Collections.sort(a);
			for(int i = 0; i < n; i++) {
				int tmp = a.get(i);
				int sum = k * (tmp / m);
				if(sum < (i + 1))
					flag = 1;
			}
			if(flag == 0)
				System.out.println("#" + t + " " + "Possible");
			else
				System.out.println("#" + t + " " + "Impossible");
		}
	}
}