계단 오르기(다이나믹 프로그래밍)

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

2579번: 계단 오르기

 

쉬운 동적 프로그래밍 기법인데 너무 빙빙 돌아서 생각했다;

 

i번째 계단에 도착하는 방법은 2가지

 

1. i-2번째 계단에서 2계단을 한 번에 올라온다.

2. i-3번째 계단에서 2계단을 한 번에 올라와 i-1번째 계단으로 온 후 i번째 계단으로 한 칸 올라온다.

 

점화식으로 정리하면 이렇게 된다

DP[i] = max(DP[i-2] + Stair[i], DP[i-3] + DP[i-1] + Stair[i])

 

i-2번째 계단에서 i-1번째 계단으로 한 칸 올라온다면 i번째 계단은 3연속이 되기 때문에 성립하지 않는다.

 

문제에서 점화식을 도출하는 연습을 꼭 해두자.

 

#include<iostream>
using namespace std;

int Stair[301] = { 0, };
int DP[301] = { 0, };

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int cmd;
	cin >> cmd;
	for (int i = 1; i < cmd + 1; i++)
	{
		cin >> Stair[i];
	}

	DP[1] = Stair[1];
	DP[2] = Stair[1] + Stair[2];
	if (cmd > 2)
	{
		for (int i = 3; i < cmd + 1; i++)
		{
			DP[i] = max(DP[i - 3] + Stair[i - 1] + Stair[i], DP[i - 2] + Stair[i]);
		}
	}
	cout << DP[cmd] << '\n';
}