백준 21600, 계단

개요

문제 링크
실버 1, DP

히스토그램 안에 들어갈 수 있는 계단 모양 도형의 최대 길이

---

접근

1. N = 100000 이므로 O(n)에 해결해야 함 전처리를 어떻게 하지?
2. i번째를 기준으로 바라볼 때, dp에 지금 위치까지 놓을 수 있는 계단의 최대높이를 저장
3. 그리고 왼쪽하고만 비교하면 됨. 비교 방식은 왼쪽 최대 높이+1 보다 크면 갱신
4. 얼핏 O(n^2)이 필요하지 않을까 생각하기 쉬운 문제, 이게 되는 이유는
   1) 왼쪽높이+1이 히스토그램 보다 낮으면 어차피 새로운 계단을 만들 수 없음. 왼쪽 계단을 그대로 가져갈 수밖에.
   2) 히스토그램이 더 낮으면 왼쪽 계단을 사용할 수 없음, 대신 1~현재 높이까지 계단은 사용가능, 왜냐? 어차피 왼쪽 높이는 현재 높이보다 높기 때문. 1~h-1까지가 왼쪽 구간에서 모두 커버됨

---

Pseudo code

dp[i] = 계최높
if (왼쪽높이+1 보다 현재 히스토그램이 높을때)
    // 왼쪽 계단을 그대로 가져감
    dp[i] = 왼쪽높이 +1
else
    dp[i] = 자신의 히스토그램 높이로 초기화

---

Source code

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a;
    int dp[n+1];
    dp[0] = 0;
    int ans = 0;
    for (int i=1; i<=n; i++) {
        cin >> a;
        dp[i] = min(dp[i-1]+1, a);
        ans = max(ans, dp[i]);
    }
    cout << ans;
}