[백준 C++] 2579 : 계단 오르기

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

다이나믹 프로그래밍을 이용해서 풀어야 하는 문제이다.

 

---

#include <iostream>
#include <vector>

using namespace std;

vector<int> stair;
vector<int> answer;
int num;

void init()
{
	cin >> num;

	answer = vector<int>(num + 1, -1);
	stair = vector<int>(num + 1, -1);

	for (int i = 1; i < num + 1; i++)
	{
		int temp;
		cin >> temp;

		stair[i] = temp;
	}
}

void solve()
{
	answer[1] = stair[1];
	answer[2] = answer[1] + stair[2];
	answer[3] = max(stair[1] + stair[3], stair[2] + stair[3]);

	for (int i = 4; i < num + 1; i++)
		answer[i] = max(answer[i - 2] + stair[i], answer[i - 3] + stair[i - 1] + stair[i]);
}

int main()
{
	init();

	solve();

	cout << answer[num] << endl;

	return 0;
}

 

각 계단에 대한 값을 저장하는 stair, 점화식을 구성하여 계산할 최대 점수 값을 저장하는 answer 벡터를 준비하였다.

 

answer[1]은 첫번째 계단만 올라가는 것이기 때문에 stair[1]이다.

answer[2]는 첫번째 계단까지의 최댓값 answer[1]과 stair[2]를 더한 값이 최대일 것이다.

answer[3]같은 경우는 두 가지 경우가 존재하는데, 1 - 3번 순으로 계단을 올라가는 것이냐, 2 - 3번째 계단 순으로 올라가는 것이냐 두가지 방법이 있다. 이는 Max함수를 이용하여 구할 수 있다.

 

answer[4]부터가 이제 잘 생각해봐야 하는 구간이다.

연속으로 3개의 계단을 밟아서는 안되기 때문에 나올 수 있는 경우는 answer[1] (첫번째 계단까지의 최댓값) + stair[3] + stair[4]이거나, answer[2] (두번째 계단까지의 최댓값) + stair[4]이다.

이를 점화식으로 구해보면 다음과 같다.

answer[N] = max( answer[N - 3] + stair[N - 1] + stair[N], answer[N - 2] + stair[N] ) 이다.

 

이 식을 이용하여 계산하면 된다.