[백준] 2579번 계단 오르기

2579번: 계단 오르기

조건을 요약해보면

 

1. 1칸, 2칸만 이동할 수 있다.

2. 연속해서 1칸을 두 번 가는 것은 불가능하다.

3. N번째 칸은 무조건 밟아야 한다.

 

즉, i번째 칸에 있는 상태는

1칸 전을 밟고 온 상태 거나 2칸 전을 밟고 온 상태, 총 두 가지 경우가 나온다.

전자를 stair[0][i], 후자를 stair[1][i]라고 표현을 해본다면

 

stair[0][i]의 1칸 전은 stair[0][i-1]과 stair[1][i-1]이다.

그러나 1칸을 연속해서 이동할 수 없으므로 stair[0][i-1]은 제외시켜준다.

그렇게 되면 stair[0][i] = 현재 계단의 점수 + stair[1][i-1]이 된다.

 

stair[1][i]의 2칸 전은 stair[0][i-2]과 stair[1][i-2]이다.

이 때는 제약 조건이 없으므로 이 둘 중 최댓값으로 계산하면 된다.

그렇게 되면 stair[0][i] = 현재 계단의 점수 + 최댓값(stair[0][i-2], stair[1][i-2])이 된다.

 

문제에 있는 예제를 표로 정리해보면 이렇게 나타낼 수 있다.

 

	0	1	2	3	4	5
0	10	20 + 10 = 30	15 + 20 = 35	25 + 25 = 50	10 + 55 = 65	20 + 45 = 65
1	10	20 + 최댓값(0,0) = 20	15 + 최댓값(10,10) = 25	25 + 최댓값(30,20) = 55	10 + 최댓값(35,25) = 45	20 + 최댓값(50,55) = 75

 

이대로 구현해주면 끝

#include <iostream>
#include <algorithm>
using namespace std;
long long stair[2][301] = { 0 };

int main() {
	int N;
	cin >> N >> stair[0][0];
	stair[1][0] = stair[0][0];
	
	int temp;
	for (int i = 1; i < N; i++) {
		cin >> temp;
		stair[0][i] = temp + stair[1][i - 1];
		stair[1][i] = temp + max(stair[0][i - 2], stair[1][i - 2]);
	}

	cout << max(stair[0][N - 1], stair[1][N - 1]);

	return 0;
}