BOJ 16615 : Dropping Blocks

• 문제 링크 : boj.kr/16615
• 난이도 : G2
• 태그 : 애드혹

---

코드

#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;
    cin >> n;
    vector<int> arr(n);
    for(auto &u : arr) cin >> u;
    
    int cnt = 0;
    for(int i = 1; i < n; i++) {
        if(arr[i] > arr[i-1]) {
            cnt += arr[i]-arr[i-1];
        }
        if(arr[i] < cnt) {
            cout << "NO";
            return 0;
        }
    }

    reverse(all(arr));
    cnt = 0;
    for(int i = 1; i < n; i++) {
        if(arr[i] > arr[i-1]) {
            cnt += arr[i]-arr[i-1];
        }
        if(arr[i] < cnt) {
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";

    return 0;
}

---

풀이

연산을 오른쪽 끝까지 놓는 것과 왼쪽 끝까지 놓는 것 두 가지로 나눌 수 있다.

우선은 오른쪽 끝까지 놓는 연산만 고려해보자.

k번째부터 오른쪽 끝까지 놓는 연산을 수행하면, k-1번째 칸에 놓인 블럭보다 k번째 칸에 놓인 블럭이 하나 많아진다. 따라서 우린 i-1번째 칸의 블럭보다 i번째 칸의 블럭이 더 많다면, i번째 칸에 해당 연산이 수행되었음을 알 수 있다.

i번째 칸까지 연산이 x번 수행되었다면 이후의 칸에는 블럭이 x개 이상 있어야 한다.

이 조건을 만족하고, 반대의 경우도 만족한다면 이는 가능한 경우이다.