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

• 문제 링크 : boj.kr/27447
• 난이도 : G5
• 태그 : 그리디

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;

    vector<int> cs(n);
    for(int i = 0; i < n; i++) {
        cin >> cs[i];
    }
    sort(all(cs), greater<int>());

    int l = cs[0]+1;
    vector<int> arr(l, -1);
    for(int i = 0; i < n; i++) arr[cs[i]] = 1;

    int idx = l;
    int ci = 0;
    while(ci < n && idx >= 0) {
        if(idx > cs[ci]) idx = cs[ci];
        if(arr[idx] == -1) {
            if(cs[ci] - idx <= m) {
                arr[idx] = 0;
                ci++;
            }
        }
        idx--;
    }

    int tcnt = 0;
    int ccnt = 0;
    for(int i = 0; i < l; i++) {
        if(arr[i] == -1) tcnt++;
        else if(arr[i] == 0) tcnt--, ccnt++;
        else ccnt--;

        if(tcnt < 0 || ccnt < 0) {
            cout << "fail";
            return 0;
        }
    }
    cout << "success";
    return 0;
}

---

풀이

타이밍과 순서에 영향을 받지 않는 행동이 딱 하나 있다. 토기를 만드는 것이다.

따라서 토기를 최대한 미리 만들어 두는 것이 이득이 될 것임을 알 수 있다.

K초에 발생할 주문을 위해 토기에 커피를 담는 것은, K-M초부터 K-1초 사이 아무때나 담아도 된다.

하지만 앞에서 발견한 사실에 따라 최대한 주문과 가까운 시간에 커피를 담아야 한다.

커피를 제공하는 행동은 정해져있으니 확인할 필요가 없다.

 

위에서 발견한 사실을 통해 가장 먼 미래의 주문부터 시간을 앞으로 당겨가며 행동을 배치하면 최적으로 행동할 수 있다.

최적으로 행동했을 때 커피를 제공하지 못한다면 fail을 출력한다.