백준 2579 C++ - 계단 오르기

Intro

소스코드

#include <iostream>
#include <algorithm>

using namespace std;

int scores[301];		// .. 계단별 점수
int dp[301];			// .. 결과

int main(void)
{
	int stair;			// .. 계단의 수
	cin >> stair;

	for (int i = 1; i <= stair; i++)
	{
		cin >> scores[i];
	}
	
	/*					<문제해결> 
		규칙1. 3개의 계단을 연속으로 밟으면안된다.
		규칙2. 한번에 두개의 계단도 오를 수 있다.
		규칙3. 마지막 계단은 무조건 밟아야한다.

		위 규칙을 따른다면 나올 수 있는 경우의 수는 2가지이다.
		N개의 계단에서
		1. N-2번째 계단을 반드시 밟고 N번째 계단을 밟는 경우
		2. N-3번째 계단을 반드시 밟고, N-1번째 계단을 밟고, N번째 계단을 밟는 경우

		1과 2중에 점수가 더 높은 방법을 택하면 된다.
	*/ 

	// .. 기저값
	dp[1] = scores[1];				
	dp[2] = scores[1] + scores[2];
	dp[3] = max(scores[1] + scores[3], scores[2] + scores[3]);


	for (int i = 4;i <= stair;i++)
	{
		// .. 점화식설정
		dp[i] = max(dp[i - 3] + scores[i - 1] + scores[i], dp[i - 2] + scores[i]);
	}

	cout << dp[stair];

	return 0;
}