[ DP - 2579 ] 계단 오르기

문제

---

접근법

 

DP 문제이다 직접 해보자.

 

문제를 요약 해 보자면 한번에 한칸 혹은 두칸을 움직일 수 없으며, 3칸 연속으로 움직일 수 없다.

즉, 출발 위치가 아닌 특정한 위치에서 한칸 움직였다면, 무조건 두칸을 움직여야 하며, 두칸 움직였다면 무조건 한칸 움직여야 한다. 

 

이러한 규칙을 발견했으므로, 가능한 경우에수는 총 4가지로 추릴 수 있다. 

1. 시작 위치에서 1칸 움직임
   1. +1, +2 의 순서로 움직임 
   2. +2, +1 의 순서로 움직임 
2. 시작 위치에서 2칸 움직임  
   1. +1, +2 의 순서로 움직임
   2. +2, +1 의 순서로 움직임

하지만 이를 코드적으로 표현하기가 힘들다.

 

0 1 2 4 5 7 ...

0 1 3 4 6 7 ...

0 2 3 5 6 8 ...

0 2 4 5 7 8 ...

 

하나의 for 문으로 4가지 모두에 대해서 점화식으로 표현하기에는 무리가 있고, +1/+2의 규칙이 있지만 각 경우의 수에서 동일한 계단위치에서의 연산이 포함되어야 하기 때문에 코드적으로 표현하기 힘들다.

 

따라서 거꾸로 생각 해 봤다.

특정한 계단에 위치하기 위해서는 한칸 전의 계단을 밟고와야 하고, 그러기 위해서는 3칸 전의 계단을 밟아야 연속으로 3칸 계단을 밟으면 안되는 규칙을 지킬 수 있다.

혹은 두칸 전의 계단을 밟는 경우는 제한 사항이 없다.

 

따라서 이를 이용하여 두 경우 중 큰 값만 저장해서 가져오면 된다. 이를 코드적으로 구현 해 보자.

ars32_MaxPoint[s32_I] = max(ars32_MaxPoint[s32_I - 3] + ars32_Stair[s32_I - 1] + ars32_Stair[s32_I], ars32_MaxPoint[s32_I - 2] + ars32_Stair[s32_I]);

 

---

정답

#include<iostream>
#include<algorithm>
using namespace std;

int32_t ars32_Stair[301];
int32_t ars32_MaxPoint[301];

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

	int32_t s32_N, s32_I;

	cin >> s32_N;

	for (s32_I = 1; s32_I <= s32_N; s32_I++)
	{
		cin >> ars32_Stair[s32_I];
	}

	ars32_MaxPoint[0] = 0;
	ars32_MaxPoint[1] = ars32_Stair[1];
	ars32_MaxPoint[2] = max(ars32_Stair[2], ars32_Stair[1] + ars32_Stair[2]);

	for (s32_I = 3; s32_I <= s32_N; s32_I++)
	{
		ars32_MaxPoint[s32_I] = max(ars32_MaxPoint[s32_I - 3] + ars32_Stair[s32_I - 1] + ars32_Stair[s32_I], ars32_MaxPoint[s32_I - 2] + ars32_Stair[s32_I]);
	}

	cout << ars32_MaxPoint[s32_N];

	return 0;
}