[C++] BOJ 2579 계단 오르기

문제

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

2579번: 계단 오르기

코드

#include<iostream>
#include<algorithm>
using namespace std;

// 0: 앞계단 안밟음(1연), 1: 앞계단 밟음(2연)
int dp[305][2];

int main() {
	int n;
	cin >> n;
	
	cin >> dp[1][0];
	dp[1][1] = dp[1][0];

	cin >> dp[2][0];
	dp[2][1] = dp[1][0] + dp[2][0];
	for (int i = 3; i <= n; i++) {
		int num; cin >> num;
		dp[i][0] = max(dp[i - 2][0], dp[i - 2][1]) + num;
		dp[i][1] = dp[i - 1][0] + num;
	}
	cout << max(dp[n][0], dp[n][1]);
}

풀이방법

전형적인 Dynamic Programming 문제다. 3번연속 밟는 것과, 3칸 이상 뛰어넘는 것이 불가능하므로 이를 고려하여 구현해준다. dp배열의 0인덱스 열은 앞 계단을 밟지 않는 경우, 1인덱스 열은 앞 계단을 밟는 경우로 나누어, 각 계단을 밟을 때의 최댓값을 저장한다.

예를 들어, (i-1)번째 계단과 i번째 계단 모두를 밟는 경우, (i-2)번째 계단을 밟지 않아야만 한다(3칸 연속 밟을 수 없음). 따라서 해당 경우의 최댓값, 즉 dp[i][1]의 값은 dp[i-1][0] +  num값이 된다.

(i-1)번째 계단을 밟지 않고 i번째 계단을 밟는 경우, (i-2)번째 계단을 밟아야만 한다(3칸 이상 건너뛸 수 없음). 따라서 해당 경우의 최댓값, 즉 dp[i][0]의 값은 max(dp[i - 2][0], dp[i - 2][1]) + num값이 된다.

 

(참고: max함수는 algorithm라이브러리를 이용해 사용할 수 있다)