Codeforces #1501B Napoleon Cake

문제

https://codeforces.com/problemset/problem/1501/B

걸린 시간

01 : 10 : 09

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int n;
        cin >> n;
        vector<int> a(n);
        for(auto& i : a) cin >> i;
        // left = first, right = second
        vector<pair<int, int>> interval(n, make_pair(0, 0)); 
        for(int i = 0; i < n; i++){
            if(a[i] == 0) continue;
            interval[max(0, i-(a[i]-1))].first++;
            interval[i].second++;
        }
        stack<int> s;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < interval[i].first; j++) s.push(1);
            if(s.empty()) cout << 0 << " ";
            else cout << 1 << " ";
            for(int j = 0; j < interval[i].second; j++) s.pop();
        }
        cout << "\n";
    }
    return 0;
}

n개의 빵을 하나씩 차례로 쌓아 올리면서 가끔은 일정량의 크림도 바르려고 한다. 크림은 양은 0을 포함한 양의 정수 a 로 주어지는데 바르는 빵을 포함 a 번째 아래에 있는 빵들까지 뒤덮는다. i 번째의 빵에 바를 크림의 양이 주어질 때 크림에 젖은 빵을 1 로 그렇지 않은 빵을 0 으로 쌓여져 있는 n개의 빵을 출력하는 것이 목표이다.

크림의 양에 따라서 크림으로 뒤덮여지는 n개의 구간을 구한 뒤, stack 자료구조를 이용하여 크림이 발라져 있는 범위를 판단하였다. 소괄호 ( ) 만으로 구성된 괄호 검사와 같다. 스택이 비어 있으면 크림이 발라져 있지 않은 것이다.

자료구조 문제를 풀이했는데 정렬, dp 로 푸는 방법도 있다고 한다.