백준 2579: 계단 오르기

문제 요약

시작점으로부터 꼭대기까지의 각 계단에는 점수가 적혀있는데, 맨 마지막 계단을 밟기까지 얻는 점수의 최댓값을 출력한다.
단, 다음의 규칙이 성립한다.
1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

문제 분류

• 다이나믹 프로그래밍

문제 풀이

문제에서 중요한 점은 맨마지막 계단은 '무조건' 밟는다는 점이다. 그러면 맨 마지막 계단으로 어떻게 왔을까? 를 생각해보면 된다. 연속하여 계단을 밟을 수는 없으므로, 바로 밑 계단과 그 2칸 밑의 계단을 모두 밟거나, 2칸 밑의 계단만을 밟아서 올라왔거나. 둘 중 하나이므로 두 경우중의 최댓값으로 계산하면 된다.

마지막으로 경계 조건은 세 가지로 나뉜다.
현재 위치가 첫 번째 계단인 경우, 해당 계단의 점수를 반환한다.
현재 위치가 두 번째 계단인 경우, 첫 번째 계단의 점수와 두 번째 계단의 점수를 합한다.
현재 위치가 세 번째 계단인 경우, 첫 번째 계단의 점수와 두 번째 계단의 점수의 최댓값과 자신의 점수를 합하여 반환하면 된다.

풀이 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int dp[301] = { 0 }, n;
vector<int> v;

int solve(int i)
{
	if (dp[i] != 0) return dp[i];
	if (i >= 3) dp[i] = v[i] + max(v[i - 1] + solve(i - 3), solve(i - 2));
	else {
		if (i == 0) dp[i] = v[0];
		if (i == 1) dp[i] = v[0] + v[1];
		if (i == 2) dp[i] = max(v[0], v[1]) + v[2];
		return dp[i];
	}
	return dp[i];
}

int main() {
	int input;
	cin >> n;
	for (int i = 0; i < n; i++) {
		scanf("%d", &input);
		v.push_back(input);
	}
	cout << solve(n - 1);
}