[swea-D3] 1860. 진기의 최고급 붕어빵

# [swea-D3] 1860. 진기의 최고급 붕어빵

🙋‍♂️ 들어가며

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

대기하는 손님의 시간배열은 꼭 정렬을!

그리고 0초부터 손님이 올 수 있다.

3 10 2
10 11 21

이 test case를 보자 이건 possible이다.

손님 도착 시간 배열은 반드시 정렬해야 한다. 정렬된 배열은 시간 순서대로 손님이 도착하는 상황을 의미한다.

먼저 time[i] < M 이라면 첫 붕어빵도 완성되지 않았으므로 Impossible이다.

이후 현재 시간까지 몇 번 생산되었는지 확인한다.

cur_mod = time[i] / M;

만약 cur_mod > prev_mod 라면 이전 손님 이후 새롭게 붕어빵이 생산된 경우이다.

따라서:

(cur_mod - prev_mod) * K

를 통해 새롭게 생산된 붕어빵 개수를 구해 extra에 더하고, 현재 손님에게 1개 제공하기 위해 extra–를 수행한다.

마지막으로:

prev_mod = cur_mod;

로 갱신한다.

반대로 cur_mod <= prev_mod 라면 새롭게 생산된 붕어빵이 없는 경우이므로, extra < 1 이면 Impossible, 그렇지 않다면 extra–를 수행한다.

✅ 코드

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
 
import java.util.Arrays;
 
public class Solution { 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc < T+1; tc++) {
            String[] NMK = br.readLine().split(" ");
            String[] t_arr = br.readLine().split(" ");
             
            int N = Integer.parseInt(NMK[0]);
            int M = Integer.parseInt(NMK[1]);
            int K = Integer.parseInt(NMK[2]);
            int[] t = new int[N];
            for (int i = 0; i < N; i++) {
                t[i] = Integer.parseInt(t_arr[i]);
            }
             
             
            // 1-1. 1중반복문
            Arrays.sort(t);
             
            // 1-2. 초기 갯수 확보
            int extra = 0;
            int prev_mod = 0;
            boolean can_you_offer = true;
            for (int i = 0; i < N; i++) {
                int cur_time = t[i];
                 
                // 2-1. 제작시간보다 사람이 더 빨리오면 불가능
                if (cur_time < M) {
                    can_you_offer = false;
                    break;
                }
                 
                // 2-2. 사람이 재때 맞춰올떄
                 
                // 2-3. 몫을 활용해 나눠줄 수 있나 보자 
                int cur_mod = cur_time / M;
                if (cur_mod > prev_mod) {
                     
                    // 2-3-a. 이전 시간의 생산량과 겹치지 않게 차감
                    int cur_extra = (cur_mod - prev_mod) * K;
                    extra += cur_extra;
                    extra--;
                     
                    // 2-3-b. 갱신
                    prev_mod = cur_mod;
                }
                else if (cur_mod <= prev_mod) {
                    if (extra >= 1) {
                        extra--;
                    }
                    else if (extra < 1) {
                        can_you_offer = false;
                        break;
                    }
                }
            }
            // 3. 출력
            if (can_you_offer) {
                System.out.println("#" + tc + " " + "Possible");
            }
            else if (!can_you_offer) {
                System.out.println("#" + tc + " " + "Impossible");
            }
             
        }
         
         
    }
}