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

문제

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

2579번: 계단 오르기

---

문제 요약

계단 오르기 게임은 계단 시작점에서 꼭대기에 위치한 도착점까지 가는 게임이다.

 

계단에는 해당 계단 층의 점수가 쓰여 있고, 밟으면 그 점수를 획득한다.

 

< 규칙>

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다.

2. 연속된 세 계의 계단을 모두 밟아서는 안된다. (단, 시작점은 포함 x)

3. 마지막 도착 계단은 반드시 밟아야 한다.

 

오를 계단 정보를 받고, 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

---

코드

#include <iostream>

#define MAX 300

using namespace std;

int scores[MAX + 1]; // i번째 계단을 밟을 경우 얻을 수 있는 점수
int n;
int dp[MAX + 1]; // dp[i]: i번째 계단까지 왔을 때, 얻을 수 있는 최대 점수

int main() {
	cin >> n;

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

	dp[1] = scores[1];
	dp[2] = scores[1] + scores[2];

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

	cout << dp[n];
}

---

코드 설명

i번째 계단까지 왔을 때, 얻을 수 있는 최대 점수는 두 가지 경우에 발생할 수 있다.

 

1. 직전에 계단 두 칸을 올라온 경우

= i - 2번째 계단까지 얻을 수 있는 최대 점수에 i번째 계단을 밟았을 때 얻을 수 있는 점수를 더한 값

=> dp[i - 2] + scores[i]

 

2. 직전에 계단 한 칸을 올라온 경우 (그 전에는 두 칸을 올라왔어야 함)

= i - 3번째 계단까지 얻을 수 있는 최대 점수에 i - 1번째 계단을 밟고, i번째 계단을 밟았을 때 얻을 수 있는 점수를 더한 값

=> dp[i - 3] + scores[i - 1] + scores[i]

 

이 두가지 경우의 수 중 더 큰 점수가 i번째 계단까지 왔을 때, 얻을 수 있는 최대 점수이다. (dp[i])