C++ 2579번(계단 오르기)

#include <iostream>

using namespace std;

int DP[1000][2];

int main(void)
{
	int a=0;
	cin>>a;
	
	for(int i=1; i<=a; i++)
	{
		int num=0;
		cin>>num;
		DP[i][0]=num;
		DP[i][1]=num;
	}
	
	
	for(int i=2; i<=a; i++)
	{
		DP[i][0]=DP[i-1][1]+DP[i][0];
		
		if(DP[i-2][0]>DP[i-2][1])
		{
			DP[i][1]=DP[i-2][0]+DP[i][1];
		}
		else
		{
			DP[i][1]=DP[i-2][1]+DP[i][1];
		}
	}
	
	if(DP[a][0]>DP[a][1])
	{
		cout<<DP[a][0];
	}
	else
	{
		cout<<DP[a][1];
	}

	return 0;
}

이 문제는 계단 오르기 문제이다.

조건은 3개이다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

(만약 1 100000 100000 2 3 이렇게 계단이 있다면 0->2->3->5가 최대가 된다.)

 

나는 문제를 해결하기 위해 int DP[1000][2]; 이차원 배열을 선언하였다.

DP[i][0] 이 부분은 i번째 계단이 이전 계단을 타고 올라왔을 때이고

DP[i][1] 이 부분은 i번째 계단이 이이전 계단을 타고 올라왔을 때이다.

 

DP[i][0]=DP[i-1][1]+DP[i][0];

만약 i번째 계단이 이전 계단을 타고 올라왔다면 이전 계단은 이이전 계단을 타고 올라와야한다.(만약 이전 계단이 이전 계단을 타고 올라오면 3개가 연속함)

 

if(DP[i-2][0]>DP[i-2][1])
{
DP[i][1]=DP[i-2][0]+DP[i][1];
}
else
{
DP[i][1]=DP[i-2][1]+DP[i][1];
}

만약 i번째 계단이 이이전 계단을 타고 왔다면 여기서는 경우의 수가 2개가 존재한다. 이이전 계단이 이전 계단을 타고 올라왔거나 아니면 이이전 계단을 타고 올라왔거나.

 

문제의 핵심은 이전 계단을 타고 올라온 값과 이이전 계단을 타고 올라온 값을 저장하는 것이다. 두 값을 모두 고려해야한다.