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

www.acmicpc.net/problem/2579

2579번: 계단 오르기

점화식을 생각하는 데 오래 걸렸던 문제입니다. 핵심은 현재 계단을 밟을 때 몇 칸을 올라왔는지 기억하며 풀어야 한다는 것입니다.

	1번 계단(10)	2번 계단(20)	3번 계단(15)	4번 계단(25)	5번 계단(10)	6번 계단(20)
1칸 올라 도달	10	30	35	50	65	65
2칸 올라 도달		20	25	55	45	75

예를 들어 4번 계단을 봅시다. 4번 계단을 밟을 수 있는 경로는 3번 계단에서 1칸 올라 밟거나 2번 계단에서 2칸 올라 밟는 것뿐입니다. 다만 1칸 올라 밟는 경우 3번 계단에서 2칸 올라 도달한 경우에만 4번 계단을 밟을 수 있습니다. 왜냐하면 3번 계단에서 도달한 경우는 이미 2개의 계단을 연속해서 밟았으므로(2 → 3번 계단) 3개의 계단을 연속해서 밟게 되는 것이기 때문에 문제의 조건을 어기게 됩니다. 2칸을 올라 밟는 경우 2번 계단에서 1칸 올라 도달한 경우와 2칸 올라 도달한 경우 모두 고려할 수 있기 때문에 max(30, 20) + 25 = 55가 됩니다. 즉 큰 값에 현재 값을 더해주면 됩니다.

#include<iostream>

using namespace std;

#define MAX 301

int DP[MAX][3];

int main(void)
{
    int n; cin >> n;
    
    for (int i = 1; i <= n; i++) {
        int temp; cin >> temp;
        if (i == 1) DP[1][1] = temp;
        else if (i == 2) {
            DP[2][1] = DP[1][1] + temp;
            DP[2][2] = temp;
        }
        else {
            DP[i][1] = DP[i - 1][2] + temp;
            DP[i][2] = max(DP[i - 2][1], DP[i - 2][2]) + temp;
        }
    }

    cout << max(DP[n][1], DP[n][2]);

    return 0;
}