[BOJ][C++] 백준 2579번: 계단오르기

문제

https://www.acmicpc.net/problem/2579

 

문제 이해

점수가 쓰여 있는 계단을 밟는 게임에서 얻을 수 있는 총 점수의 최댓값을 구한다.

 

계단 오르는 규칙

1. 한 번에 한 계단 또는 두 계단씩 오를 수 있다.
2. 연속된 세 계단을 밟으면 안 된다.
3. 마지막 도착 계단은 반드시 밟아야 한다.
4. 시작점은 계단에 포함되지 않는다.

 

문제 풀이

🔍 접근

각 계단마다 현재 계단까지의 점수 최댓값을 구해서 저장한다.

 

💡 Dynamic Programming

각 계단은 1칸 또는 2칸 전 계단에서 온 것이므로 max(1칸 전 최댓값, 2칸 전 최댓값) + 현재 계단 점수로 식을 세울 수 있다.

하지만 연속 세 칸을 밟으면 안 되는 조건을 만족하지 못한다.

이 조건을 고려해서 경우의 수를 생각해보면 아래와 같이 나타낼 수 있다.

• 2칸 전 최댓값 이용: 연속 세 칸 안 밟음
• 1칸 전 값 이용: 3칸 전 →1칸 전을 밟은 경우는 연속 세 칸 안 밟음

max(2칸 전 최댓값, 1칸 전 값 + 3칸 전 최댓값) + 현재 계단 점수로 식을 세울 수 있다.

 

코드

#include <iostream>
#include <vector>

using namespace std;

int maxScore(int n, vector<int> &score)
{
	vector<int> dp(n + 1, 0);

	dp[1] = score[1];
	if (n > 1)
		dp[2] = score[1] + score[2];

	for (int i = 3; i <= n; i++)
		dp[i] = max(dp[i - 2], dp[i - 3] + score[i - 1]) + score[i];

	return dp[n];
}

int main()

{
	int n;
	vector<int> score;

	cin >> n;
	score.assign(n + 1, 0);

	for(int i= 1; i <= n; i++)
		cin >> score[i];
	
	cout << maxScore(n, score);
    
	return 0;
}