백준 21600
-
백준 21600: 계단코딩 2021. 7. 17. 12:30
https://www.acmicpc.net/problem/21600 21600번: 계단 자료의 분포를 아래의 그림과 같이 나타낸 그래프를 히스토그램이라고 합니다. 당신은 히스토그램 영역에서 가장 큰 계단을 찾으려고 합니다. 계단은 아래 조건을 만족하는 영역을 말합니다. www.acmicpc.net 문제는 위와 같습니다. 풀이 히스토그램에서 가장 왼쪽의 높이부터 차례대로 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$가 됩니다. 만..