[백준 C++] 2579 계단 오르기 - 다이나믹프로그래밍

2579번: 계단 오르기

#include <iostream>
using namespace std;

int StairScores[301];
int DP[301];

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

	int N;
	cin >> N;
	for (int i = 1; i <= N; ++i)
	{
		cin >> StairScores[i];
	}

	DP[1] = StairScores[1];
	DP[2] = StairScores[1] + StairScores[2];
	DP[3] = max(StairScores[1] + StairScores[3], StairScores[2] + StairScores[3]);
	for (int i = 4; i <= N; ++i)
	{
		DP[i] = max(DP[i - 2] + StairScores[i], DP[i - 3] + StairScores[i - 1] + StairScores[i]);
	}

	cout << DP[N];
}

---

 

다이나믹 프로그래밍 유형의 문제로 점화식을 도출해내는 것이 중요한 문제입니다.

각 계단의 점수를 담은 배열과 해당 계단까지의 점수 최대값을 저장하는 배열을 사용해서 풀었습니다.

점화식 도출 과정은 다음과 같습니다.

 

1. 먼저 계단 1~3의 최대값을 저장해줍니다.

2. 계단 4 부터는 이전 계단을 밟았는지 밟지 않았는지의 경우로 나누어서 둘 중 최대값을 선택하는 것으로 일반화합니다.

3. 이전 계단을 밟지 않았을 경우는 2 단계 밑의 계단의 최대값과 해당 계단의 점수를 더해줍니다.

4. 이전 계단을 밟았을 경우는 3 단계 밑의 계단의 최대값과 이전 계단의 점수, 그리고 해당 계단의 점수를 더해줍니다.

5. 두 경우 중에 큰 값을 해당 계단까지의 점수의 최대값으로 선택합니다.