백준 21600: 계단

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

21600번: 계단

문제는 위와 같습니다.

 

 

풀이

히스토그램에서 가장 왼쪽의 높이부터 차례대로 a[0], a[1], a[2], ...라고 합니다.

dp[i]를 (a[i]가 계단의 가장 오른쪽인 계단의 최대 높이)라고 합시다.

점화식을 구해봅시다.

만일 a[i]가 dp[i-1]+1 이상이라면, a[i]가 높이 dp[i-1]+1인 계단의 가장 오른쪽 사각형이 될 수 있고, 그것이 최대이므로 $dp[i]=dp[i-1]+1$가 됩니다.

만일 a[i]가 dp[i-1] 이하라면, a[i]가 계단의 가장 오른쪽 높이가 되는 것이 최대이므로 $dp[i]=a[i]$가 됩니다.

정리해보면

$$dp[i]=\begin{cases}dp[i-1]+1 &(a[i]>dp[i-1])\\ a[i] & (a[i] \leq dp[i-1])\end{cases}$$

가 나오게 됩니다. (단, $dp[0]=1$)

 

코드

위의 풀이로 짠 코드입니다.

#include <bits/stdc++.h>
using namespace std;
int a[100000], dp[100000];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m=1;
    cin >> n;
    dp[0]=1;
    for(int i=0; i<n; i++) {
        cin >> a[i];
        if(i) {
            if(a[i]>dp[i-1]) dp[i]=dp[i-1]+1;
            else dp[i]=a[i];
        }
        m=max(m, dp[i]); //최대 계단 구하기
    }
    cout << m;
}

 

감사합니다.