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

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

2579번: 계단 오르기

---

문제 풀이

 문제에서 마지막 계단은 무조건 밟아야 한다는 조건을 주었다. 그렇다면 주어진 경우는

  1. 마지막 계단의 전 계단을 밟는 경우

  2. 마지막 계단의 전전 계단을 밟는 경우

dp 배열은 n번째 계단에서 나올 수 있는 최댓값을 저장한다. 그렇다면 점화식은 주어진 경우에 따라

  1번 경우 → N번째 계단 + (N-1)번째 계단 + (N-3)번째 계단까지의 최댓값 

  2번 경우 → N번째 계단 + (N-2)번째 계단까지의 최댓값 

즉, DP[n-3] + stairs[n] + stairs[n-1] 와 DP[n-2] + stairs[n]을 비교해서 더 큰 값을 저장하면 된다. 

느낀 점

점화식만 구할 수 있다면 간단한 문제인 것 같다. 하지만 찾지 못해서 엄청 헤맸다. 계속 풀이법이 백트래킹으로만 접근이 되서 내 접근법에 문제가 조금 많이 있는 것 같다.

코드

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int stairs[301] = { 0, };
int dp[301] = { 0, };

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

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

	cout << dp[n];
}