백준 2579 계단 오르기

https://www.acmicpc.net/problem/2579

 

문제 설명에 보면 아래와 같은 조건이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

1번 조건은,

현재 n번째 계단에서 오를 수 있는 위치는 n+1, n+2 번째 계단이다.

2번 조건은,

n, n+1, n+2 계단을 동시에 밟을 수 없다는 것

3번 조건은 마지막 계단을 반드시 밟는 것

n번째 계단을 밟는 방법은

1. n-1번째 계단을 밟고 오는 경우

2. n-2번째 계단을 밟고 오는 경우

2가지로 표현 될 수 있다.

하지만 단순히 n번째 계단에 오르는 값을 max(n-1번째 계단까지의 최대값, n-2번째 계단까지의 최대값) 으로 계산하게 되면, 2번 조건을 위배하는 상황을 배제할 수 없다.

(처음에 위에 처럼 계산하였다가 계단을 몇 칸 뛰어 올라왔는 지 여부가 아닌, 각 계단의 점수를 더하여 답을 내는 것을 발견하였다... 2번 조건을 위배한 것이다. 때문에 n번째 계단을 올라올 때 1칸 뛴 경우, 2칸 뛴 경우를 생각하고자 하였고, 1차원 점화식이 아니라 2차원 배열 점화식을 세우고자 하였다.)

풀이를 시작하자면

1. n번째 계단을 1칸뛰어 올라 온 경우(dp[n][0])

2. n번째 계단을 2칸뛰어 올라 온 경우를 생각해야한다.(dp[n][1]) 

2번을 먼저 확인해보자면, n번째 계단을 2칸만에 뛰어 얻는 최대 점수는

n번째 계단 + max(n-2 계단을 1칸뛰어 올라온 경우, n-2 계단을 2칸뛰어 올라온 경우)

이다. 이를 점화식으로 표현하자면

dp[n][1] = stair[n] + max(dp[n-2][0], dp[n-2][1]) 이다.

1번은 주의해야 할 점이 있는데, n번째 계단을 1칸만에 뛰어올라오려면 n-1, n-2번째 칸을 연속으로 밟으면 안된다. 때문에 n-1번째 칸을 2칸만에 뛰어올라와야 한다.

즉, 이를 점화식으로 표현하자면

dp[n][0] = stair[n] + dp[n-1][1] 이다.

최종적으로 

n번째 계단에 있을 때, n-1번째에서 올라 온 값과, n-2번째에서 올라온 값중에 최대값을 확인하면 n번째 계단에서 가질 수 있는 최대값을 구할 수 있게 된다.

#include <iostream>
#include <cmath>
using namespace std;
int main() {
	int num = 0;
	int stair[301] = {0, };
	int dp[301][2] = {0, };
	
	cin >> num;
	
	for(int i = 1 ; i <= num ; ++i) {
	    cin >> stair[i];
	}
	
	dp[1][0] = stair[1]; // 1번째 계단을 1칸으로 올라가는 것
	dp[1][1] = stair[1]; // 1번째 계단을 2칸으로 올라가는 것
	
	for(int n = 2 ; n <= num; ++n) {
	   dp[n][0] = stair[n] + dp[n-1][1];
	   dp[n][1] = stair[n] + max(dp[n-2][0], dp[n-2][1]);
	}
	
	cout << max(dp[num][0], dp[num][1]) << endl;
 	return 0;
}