계단 (백준 21600)

안녕하세요. 오늘은 계단을 설치할 거예요.

문제

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

아이디어

이 문제의 핵심은 특정한 칸을 끝으로 하는 크기 K의 계단이 가능하면 그 칸을 끝으로 하는 크기 K-1의 계단이 가능하다는 것입니다. 그러므로 dp[i]를 i를 끝으로 하는 계단의 크기의 최댓값이라고 하면 dp[i]=min(dp[i-1]+1,arr[i])가 됩니다.

소스코드

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;


int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, x, before = 0, now = 0, mx = 0, i;

    cin >> N;
    for (i = 1; i <= N; i++)
    {
        cin >> x;
        now = min(before + 1, x);
        mx = max(mx, now);
        before = now;
    }
    cout << mx;
}

감사합니다.