백준 온라인 저지, 그리디 / 21600번: 계단 (파이썬 / 백준 실버문제)

문제 주소: https://www.acmicpc.net/problem/21600

문제

자료의 분포를 아래의 그림과 같이 나타낸 그래프를 히스토그램이라고 합니다.

당신은 히스토그램 영역에서 가장 큰 계단을 찾으려고 합니다. 계단은 아래 조건을 만족하는 영역을 말합니다.

• 계단의 ‘길이’는 계단에 포함된 히스토그램의 열의 수를 나타냅니다.
• 계단의 길이가 $L$이라고 할 때, 왼쪽에서 $i$번째 열은 높이가 $i$입니다. 즉, 맨 왼쪽 열의 높이는 1, 그 다음 열의 높이는 2이고, 맨 오른쪽 열의 높이는 $L$입니다.

히스토그램 영역이 계단을 포함하면 되기 때문에, 히스토그램의 높이가 계단의 높이 이상이기만 하면 되고, 정확히 같을 필요는 없습니다.

위 히스토그램에서 가장 큰 계단은 아래와 같습니다. 가장 큰 계단은 가장 길이가 긴 계단과 같은 의미입니다. 히스토그램이 입력으로 주어질 때, 가장 큰 계단의 길이를 구해 봅시다.

입력

첫 줄에는 히스토그램의 열의 수를 나타내는 정수 $N$이 주어집니다.

둘째 줄에는 각 열의 높이를 나타내는 정수 $A_1, A_2, \cdots, A_N$이 주어집니다.

출력

히스토그램에서 가장 긴 계단의 길이를 출력합니다.

제한

• $1 \le N \le 10^5$
• $1 \le A_i \le 10^9$

서브태스크

번호	배점	제한
1	25	$A_1 = A_2 = \cdots A_N$
2	30	$N \le 100$
3	35	$N \le 2000$
4	60	추가 제한 조건이 없습니다.

예제 입력 1

5
1 3 2 3 1

예제 출력 1

3

예제 입력 2

13
3 1 4 1 5 9 2 6 5 3 5 8 9

예제 출력 2

6

힌트

접근 방법

- 히스토그램을 하나씩 탐색해가며 계단의 최대 길이를 체크한다.
- 만약 현재 계단의 높이보다 히스토그램의 높이가 높거나 같다면 그냥 값을 더해준다.
- 만약 현재 계단의 높이보다 히스토그램의 높이보다 낮다면 그 높이만큼을 계단의 높이로 갱신하여 다시 계산한다.

코드

# https://www.acmicpc.net/problem/21600
# 접근 방법
# 히스토그램을 하나씩 탐색해가며 계단의 최대 길이를 체크한다.
# 만약 현재 계단의 높이보다 히스토그램의 높이가 높거나 같다면 그냥 값을 더해준다.
# 만약 현재 계단의 높이보다 히스토그램의 높이보다 낮다면 그 높이만큼을 계단의 높이로 갱신하여 다시 계산한다.
n = int(input())
histogram = list(map(int, input().split()))
lengthOfStair = 0
result = 0
for x in histogram:
    lengthOfStair = lengthOfStair+1 if lengthOfStair+1 <= x else x
    result = max(result, lengthOfStair)
print(result)