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

문제링크 : https://www.acmicpc.net/problem/2579

 

문제풀이

동적 계획법으로 풀 수 있는 문제이다.

 

계단 오르는 데는 다음과 같은 규칙이 있다.

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

2. 연속된 세 개의 계단을 모두 밟아서는 안 된다.

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

 

점수가 25인 계단까지 올라가려면, 아래와 같은 방법이 존재한다.

n-2 까지의 최댓값 + n

n-3 까지의 최댓값 + n-1 + n

의 식으로 25까지의 최댓값을 구할 수 있다.

 

n-1 까지의 최댓값을 구하지 않는 이유는

n-1 까지 두 개의 계단을 올라온 경우가 최댓값이라고 하면 25까지 연속해서 올라갈 수 없기 때문이다.

(아래 그림은 15까지 세 계단을 올라오는 경우라 잘못된 경우이지만, 예를 위해 넣었다.)

 

따라서,

n-2 까지의 최댓값 + n

n-3 까지의 최댓값 + n-1 + n

두 가지 방법 중 합이 더 큰 점수를 계속해서 저장해놓으면 된다.

 

 

소스코드

/*
 * 백준 2579번: 계단 오르기
 */

#include <iostream>
#include <algorithm>

using namespace std;

#define MAX 300

int stairs[MAX], dp[MAX];

int main() {
	int n;
	cin >> n;

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

	dp[0] = stairs[0];
	dp[1] = stairs[0] + stairs[1];
	dp[2] = max(stairs[0] + stairs[2], stairs[1] + stairs[2]);

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

	cout << dp[n - 1];

	return 0;
}