백준 27447 주문은 토기입니까? 자바(java)

https://www.acmicpc.net/problem/27447

27447번: 주문은 토기입니까?

 

풀이 방법

그리디 알고리즘 문제이다.

N크기의 배열 customers 을 생성하여 입력 받은 손님들의 도착 시간을 저장한다.

풀이를 위해 사용한 변수는 아래와 같다.

• togi: 현재 만들어져 있는 토기 개수
• coffee: 현재 토기에 담아 놓은 커피의 개수
• servingTarget: 현재 시점에서 가장 먼저 도착하는 손님 인덱스, 즉 서빙할 손님
• customer_idx: 배열에서의 손님 인덱스

 

시간 t=0 부터 증가시키면서 각 t초마다 일을 수행해주면 되는 데 아래 조건을 확인해주면서 각 조건에 맞게

최적의 일을 수행해준다.

1. 손님이 도착한 시간에는 무조건 서빙해야 한다.
   • t 와 serveingTarget의 도착 시간이 같은지 비교하여 같다면 서빙한다.
   • 서빙할 때 coffee 가 0보다 크다면, 즉 커피가 토기에 담아져있다면 서빙한다.
   • 그게 아니라면 즉시 서빙할 수 없으므로 fail
2. 다음 손님을 위해 미리 커피를 준비해 놓을 수 있는지 확인한다.
   • 손님이 s 시간에 도착한다고 하면 s에 서빙을 시작하여 서빙 완료 시간은 s+1
   • 커피를 t시간에 담는다고 하면 t+1 에 커피 담기가 완료되며 이후 M초 안에는 서빙되어야 한다.
   • 즉, s+1 <= t+M+1 이여야 하므로 s <= t+M 이면 t시간에 커피를 미리 담을 수 있다.
   • 커피를 담아야 하는데 담을 토기가 없다면 토기를 만들어야 하므로 togi만 증가시킨다.
   • 토기가 있다면 coffee 증가, togi 감소시키고 customer_idx 을 증가시켜 다음 손님을 본다.
3. 위에 모두 해당되지 않는다면 할게 없으므로 토기나 만든다. togi 증가

 

코드

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] customers = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            int t = Integer.parseInt(st.nextToken());
            customers[i] = t;
        }

        int togi = 0; // 현재 만들어져 있는 토기 수
        int coffee = 0; // 현재 토기에 담아놓은 커피 수
        int servingTarget = 0; // 현재 시점에서 가장 먼저 도착하는 손님
        int customer_idx = 0;
        boolean success = true;
        for(int t=0; t<customers[N-1]+1; t++) {
            // 손님이 도착하면 서빙해야 함
            if(customers[servingTarget] == t) {
                if(coffee > 0) { // 커피가 담긴 토기가 있다면
                    servingTarget++;
                    coffee--;
                } else {
                    success = false;
                    break;
                }
                // 지금 커피를 담아놓을 수 있으면 미리 커피 준비
            } else if(customer_idx < N && customers[customer_idx] <= t+M) {
                // 토기가 없으면 토기 만들기
                if(togi == 0) {
                    togi++;
                } else { // 토기가 있으면 커피 담기
                    coffee++;
                    togi--; // 토기 사용
                    customer_idx++;
                }
            } else {
                togi++; // 뭐 없으면 토기 만들기
            }

        }
        if(success) {
            System.out.println("success");
        } else {
            System.out.println("fail");
        }
    }
}