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

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	vector<int> stair;
	vector<int> dp;
	int count;
	cin >> count;

	stair = vector<int>(count, 0);
	dp = vector<int>(count, 0);

	for (int i = 0; i < count; i++)
	{
		cin >> stair[i];
	}

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

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

	cout << dp[count - 1];

	return 0;
}

 

풀이

1. 계단의 정보를 저장하고 직접 최대값이 나올 수 있는 방법을 찾아본다.

2. 직접 찾는 방법으로 dp를 만든다.

dp0 = arr0

dp1 = arr0 + arr1

dp2 = arr0 + arr2 or arr1 + arr2

dp3 = arr0 + arr1 + arr3 or arr0 + arr2 + arr3

 

해당 방법대로 공식을 세워보면

dp3 기준

dp[ i ] = dp[ i - 2 ] + arr[ i ] or dp[ i - 3 ] + arr[ i - 1 ] + arr[ i ]

위와 같은 식이 세워진다.

 

dp4까지 직접 해본다면?

(4 + 3 + 0 + 1), (4 + 0 + 2), (4 + 1 + 2)의 경우가 나온다.

마찬가지로 arr 0+2와 arr 1+2가 dp2이기 때문에 dp[ i - 2 ] + arr[ i ]가 나오고

4 + 3 + 0 + 1도 마찬가지로 0 + 1는 dp1이기에 dp[ i - 3 ] + arr[ i ] + arr[ i - 1 ]이 된다.

arr[ i ]은 무조건 독립적으로 가야하니 arr[ i - 1 ]이 남게되는 것이다.

 

해당 방법으로 계산하여 마지막 dp가 답이 된다.

 

느낀점

단순 계산을 먼저 따진 후에 해당 식을 공식으로 바꾸어 점화식을 만드는 것이 정말 중요한 것 같다.

무턱대고 막 하면 점화식을 어떻게 만들지 생각이 들지만, 차근차근 단순 계산을 해주는 것이 빠르게 풀 수 있는 좋은 접근인 것 같다.

 

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