SW Expert Academy - 1860번(진기의 최고급 붕어빵)

최지홍·2022년 5월 29일
0

SW Expert Academy

목록 보기
35/36

문제 출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LsaaqDzYDFAXc&categoryId=AV5LsaaqDzYDFAXc&categoryType=CODE&problemTitle=1860&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1


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

public class Solution {

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(reader.readLine());

        for (int t = 0; t < T; t++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

            int N = Integer.parseInt(tokenizer.nextToken());    // 인원수
            int M = Integer.parseInt(tokenizer.nextToken());    // 쿨타임
            int K = Integer.parseInt(tokenizer.nextToken());    // 붕어빵의 수

            int[] customer = new int[N];
            int maxTime = 0;

            tokenizer = new StringTokenizer(reader.readLine());

            for (int i = 0; i < N; i++) {
                customer[i] = Integer.parseInt(tokenizer.nextToken());
                maxTime = customer[i] > maxTime ? customer[i] : maxTime;
            }

            String ans = "Possible";

            int[] fishBread = new int[maxTime / M + 1];
            for (int i = 1; i < fishBread.length; i++) {
                fishBread[i] += fishBread[i - 1] + K;
            }

            for (int i = 0; i < N; i++) {
                int index = customer[i] / M;
                if (fishBread[index] > 0) {
                    fishBread[index]--;
                    if (index < fishBread.length - 1) {
                        reduce(fishBread, index + 1, fishBread.length);
                    }
                } else {
                    ans = "Impossible";
                    break;
                }
            }

            sb.append("#").append(t + 1).append(" ");
            sb.append(ans).append("\n");
        }

        System.out.println(sb);
    }

    private static void reduce(int[] target, int from, int to) {
        for (int i = from; i < to; i++) {
            target[i]--;
        }
    }

}

  • 주요 로직은, 가장 늦게 도착하는 손님의 시간을 알아내서 그 손님을 커버할 수 있는 크기 만큼의 붕어빵 배열을 만들고 각 배열 원소는 누적합으로 채운다.
  • 손님 한명을 처리할 때마다 해당 시간의 값을 뺀 뒤, 그 뒤에 있는 배열 원소들의 값들을 모두 1씩 빼서 값을 업데이트해준다.
  • 해당 시간 값을 뺄 수 없으면 "Impossible" 처리한다.
profile
백엔드 개발자가 되자!

0개의 댓글