Categories: SWEA

SWEA 1860 진기의 최고급 붕어빵 D3 (자바 Java)

java

SWEA 1860 진기의 최고급 붕어빵

문제 정보

문제 출처 : SW Expert Academy
문제 번호 : 1860
문제 제목 : 진기의 최고급 붕어빵
문제 난이도 : D3
풀이 언어 : Java

문제

진기는 붕어빵 가게를 운영하고 있다. 이 붕어빵은 예약제로만 판매되며, 오늘은 N명의 손님이 자격을 얻었습니다. 진기는 0초부터 붕어빵을 만들기 시작하며, M초마다 K개의 붕어빵을 완성할 수 있습니다. 손님들이 도착하는 시간이 주어졌을 때, 모든 손님들이 기다리지 않고 붕어빵을 받을 수 있는지 여부를 판별하는 문제

접근

손님들의 도착 시간을 배열에 저장하고 정렬한 후, 각 시간 단위마다 만들어진 붕어빵의 수를 계산하고, 각 손님의 도착 시간에 붕어빵을 제공할 수 있는지 여부를 검사했다.

풀이

테스트 케이스의 수 T를 입력 받습니다.
테스트 케이스의 수만큼 반복을 수행합니다.
각 테스트 케이스에 대해, 손님 수 N, 붕어빵을 만드는 시간 M, 한 번에 만들어지는 붕어빵 수 K를 입력 받습니다.
손님들이 도착하는 시간을 저장할 배열 times를 선언하고, 크기를 N으로 설정합니다.
손님들의 도착 시간을 times 배열에 입력 받습니다.
times 배열을 오름차순으로 정렬합니다.
모든 손님에게 붕어빵을 제공할 수 있는지 여부를 나타내는 possible 변수를 true로 초기화합니다.
첫 번째 손님의 도착 시간이 0초일 경우, possible을 false로 설정합니다.
첫 번째 손님의 도착 시간이 0초가 아닐 경우, 남은 코드를 실행합니다.
bread 변수를 0으로 초기화하고, idx를 0으로 초기화합니다(이는 현재 처리중인 손님의 인덱스).
마지막 손님의 도착 시간 lastTime을 설정합니다.
1초부터 lastTime까지 반복하면서 붕어빵을 만들고 손님들에게 제공합니다.
현재 시간이 M으로 나누어 떨어질 때마다 bread에 K만큼 더해 붕어빵을 추가합니다.
현재 시간이 손님의 도착 시간과 일치하면, 붕어빵을 하나 제공하고 idx를 증가시킵니다.
만약 붕어빵이 부족할 경우, possible을 false로 설정하고 반복을 종료합니다.
각 테스트 케이스의 결과를 출력합니다(“Possible” 또는 “Impossible”).

후기

헷갈리는 부분이 있어서 시간이 꽤 걸렸던 문제이다. 비슷한 유형의 문제를 여러 번 풀어봐야겠다.

코드

Java

import java.util.Arrays;
import java.util.Scanner;
import java.io.FileInputStream;
 
class Solution
{
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();
 
        for(int test_case = 1; test_case <= T; test_case++)
        {
            int N = sc.nextInt();
            int M = sc.nextInt();
            int K = sc.nextInt();
            int[] times = new int[N];
 
            for (int i = 0; i < N; i++) {
                times[i] = sc.nextInt();
            }
 
            Arrays.sort(times);
 
            boolean possible = true;
            if(times[0] == 0) {
                possible = false;
            } else {
                int bread = 0, idx = 0, lastTime = times[N - 1];
                for (int i = 1; i <= lastTime && possible; i++) {
                    if (i % M == 0) {
                        bread += K;
                    }
                    if (idx < N && i == times[idx]) {
                        if (bread > 0) {
                            bread--;
                            idx++;
                        } else {
                            possible = false;
                        }
                    }
                }
            }
            System.out.println("#" + test_case + " " + (possible ? "Possible" : "Impossible"));
        }
    }
}