계단 오르기 (백준 - 2579번)

동적계획법을 사용하는 문제였다.

 

규칙

1. 계단을 오른때는 1칸 또는 2칸 오를 수 있다.
2. 연속된 3칸을 오를 수 없다.
3. 마지막 계단은 무조건 밟아야한다.

 

위 3가지 규칙을 바탕으로 마지막 계단을 밟는 경우를 두가지로 분류 해볼 수 있다.

 

1. 마지막 계단을 밟고 그 전 계단을 밟는 경우
(하지만 위 규칙 2번으로 인해 무조건 전 계단을 밟은 이후 전전전 계단을 밟아야 한다.)

이 경우 점화식은 S[n] = S[n] + S[n - 1]이 된다. (위 규칙 2번으로 인해 DP[n - 3]도 더해줘야 한다.) (S는 계단의 값들을 보관하는 배열이고 DP는 계단까지의 최대값을 보관하는 DP테이블(배열)이다.)

 

2. 마지막 계단을 밟고 그 전전 계단을 밟는 경우

이 경우 점화식은 S[n] = S[n] + DP[n - 2]이 된다.

 

첫번째 계단부터 구하려는 N번째 계단까지 위 점화식 두가지 중 가장 큰 값을 DP테이블에 저장하면 DP[N]에 구하려는 최대값을 얻을 수 있다.

 

코드는 다음과 같다.

 

#include <iostream>
using namespace std;

int max(int a, int b)
{
	return a < b ? b : a;
}

int main()
{
	int input;
	cin >> input;

	int* stairs = new int[input];
	int* dp = new int[input];
	for (int i = 0; i < input; ++i)
	{
		cin >> stairs[i];
	}

	dp[0] = stairs[0];
	dp[1] = max((stairs[0] + stairs[1]), stairs[1]);
	dp[2] = max((stairs[0] + stairs[2]), (stairs[1] + stairs[2]));

	for (int i = 3; i < input; ++i)
	{
		dp[i] = max(dp[i - 2] + stairs[i], stairs[i - 1] + stairs[i] + dp[i - 3]);
	}

	cout << dp[input - 1] << endl;
	delete[] stairs;
	delete[] dp;
}