백준 2579 계단 오르기 (C++)

많은 케이스를 고려해보아야 할 dp 문제였다.

※시작점은 계단이 아니고 시작점에서 한칸 or 두칸 한번에 오를 수 있으므로 처음 닿는 칸이 두번째 칸일 수도 있다.

 

탑다운 풀이

#include <iostream>
#include <algorithm>
#include<cmath>
using namespace std;
int dp[302][3];
int arr[302];
int inputnum;
int rec(int index, int num, int continually);
int main()
{
	cin >> inputnum;
	arr[0] = 0;
	for (int i = 1; i <= inputnum; i++)
	{
		cin >> arr[i];
	}
	fill(&dp[0][0], &dp[300][2], -1);
	cout << rec(0, 0, 0);
}
int rec(int index, int num, int continually)
{
	if(continually>=3) return -2100000000;
	if (index == inputnum) return arr[index];
	if (index > inputnum) return -2100000000;
	if (dp[index][continually] != -1) return dp[index][continually];
	int temp = arr[index]+ max(rec(index + 1, num + arr[index], continually + 1), rec(index + 2, num + arr[index], 1));
	dp[index][continually] = temp;
	return temp;
}

몇번째 칸인지만이 중요한게 아니라 몇번째 칸에 도달 했을 때 계단을 연속으로 몇칸 이동중인지도 중요하므로

dp를 이차원 배열로 활용. 연속 3칸 이동할 경우 max값으로 선택되지 않도록 매우 작은 값을 return 해준다.

 

바텀업풀이

#include <iostream>
#include <algorithm>
#include<cmath>
using namespace std;
int dp[302][3];
int arr[302];
int inputnum;
int main()
{
	cin >> inputnum;
	arr[0] = 0;
	for (int i = 1; i <= inputnum; i++)
	{
		cin >> arr[i];
	}
	fill(&dp[0][0], &dp[301][2], -1);
	dp[1][1] = arr[1];
	dp[2][1] = arr[2];
	dp[2][2] = arr[2] + dp[1][1];
	
	for (int i = 3; i <= inputnum; i++)
	{
		dp[i][1] = max(dp[i - 2][1] + arr[i], dp[i - 2][2] + arr[i]);
		dp[i][2]=  dp[i - 1][1] + arr[i];
	}
	cout << max(dp[inputnum][1], dp[inputnum][2]) << endl;
}

이차원 배열의 두번째 인덱스를 연속으로 이동중인 계단 수라고 했을 때

dp[1][1]은 시작지점에서 이동하는 경우 뿐이므로 arr[1]

dp[2][1]은 시작지점에서 두칸 이동해 시작했을 경우 -> arr[2]

dp[2][2]는 첫번째칸을 거쳐서 온 경우 이므로 dp[1][1] + arr[2]

 

dp[3][1]=max(dp[1][1] + arr[3] , dp[1][2] + arr[3] ) + arr[3]

두칸을 건너뛰었을 때 연속 횟수가 초기화 되므로 dp[3][1]은 위와 같이 구할 수 있다.

dp[3][2]=dp[2][1]+arr[3]

[3][2]라면 이전 계단을 밟았을 것이므로 dp[2][1]에 세번째칸의 값을 더해주어 구해준다.

 

dp[i][1] = max(dp[i-2][1] , dp[i-2][2]) + arr[i]

dp[i][2] = dp[i-1][1] + arr[i] 라는 것을 알 수 있다.