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

1. 문제

 

 

 

2. 문제 풀이

 

다이나믹 프로그래밍 (DP) 문제이다.

현재의 상태를 저장시켜서 이를 지속적으로 활용하는 다이나믹 프로그래밍의 특성에 맞춰,

다음과 같은 문제 풀이 접근 방법을 활용하였다.

 

'각각의 계단에 대해서, 이전 계단을 선택하는 경우와, 이전의 이전 계단을 선택하는 경우를 계산해나간다.'

 

즉, 각 계단에 대해서 다음의 알고리즘을 반복하는 것이다.

 

(1) 이전 계단을 선택하는 경우, 이전 계단의 상태 중에서 '이전 계단을 선택하지 않았던 상태'를 선택할 수 있다.

-> 이전 계단 중에서, '이전 계단을 선택했던 경우'를 선택하면 연속해서 세 계단을 오른 경우이므로 선택 불가

 

(2) 이전의 이전 계단을 선택하는 경우, 이전의 이전 상태 중 더 큰 값을 선택한다.

-> 이전의 이전 계단의 경우는, 그 계단에서 어떤 계단을 선택했는지 상관없다. 연속된 케이스가 아니기 때문이다.

 

(3) 이전 계단을 선택한 경우와, 이전의 이전 계단을 선택한 경우에 각각 지금 계단의 점수를 더해준다.

 

위의 과정을 반복한 결과를 나타내면 다음과 같다.

 

 

 

 

3. 코드 (C++)

 

#include <iostream>

using namespace std;

int retMax(int a, int b)
{
	if (a > b)return a;
	else return b;
}

int main(void)
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int arr[301][3] = { 0 };

	int N;
	cin >> N;

	cin >> arr[1][0];
	arr[1][1] = arr[1][2] = arr[1][0];
	for (int i = 2; i <= N; i++)
	{
		cin >> arr[i][0];
		arr[i][1] = arr[i - 1][2] + arr[i][0];
		arr[i][2] = retMax(arr[i - 2][1], arr[i - 2][2]) + arr[i][0];
	}

	cout << retMax(arr[N][1], arr[N][2]) << '\n';

	return 0;
}