취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 21600번 문제인 계단이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/21600

이 문제에서 "계단"이 다음과 같은 성질이 있다는 것을 관찰하자:

길이가 2보다 큰 모든 "계단"은 각 열의 높이를 1씩 낮춰도 길이가 1 줄어든 "계단"이 된다.

따라서, 히스토그램의 맨 왼쪽부터 계단을 쌓아나가다가, 더 쌓을 수 없는 높이의 (낮은)막대를 만나면 이 막대를 포함하는 지금까지의 가장 길이가 큰 계단은 이 막대의 높이와 같아질 것이라는 것을 알 수 있다.

이 성질을 이용하여 가장 큰 계단의 크기를 갱신해 나간다면 문제를 간단히 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;

	int mxstair = 0;
	int stair = 0;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		if (x > stair) {
			stair++;
			if (mxstair < stair) mxstair = stair;
		}
		else stair = x;
	}

	cout << mxstair;
}