[백준] 계단오르기 2579번 (c++)

풀이 방법

반복된 계산을 줄여 풀이하는 dp 문제이다

stairs배열에는 계단의 점수를 저장하였다. (0인덱스에는 시작점)

dp배열은 dp[i] ==  i번째 계단까지 오는 최대 점수이다 (i 계단을 밞고 있어야 한다)

dp[1]은 당연히 stairs[1]이고 dp[2]는 stairs[1] + stairs[2]보다 큰 경우는 없으므로 stairs[1] + stairs[2]가 된다.

그럼 dp[3]은 stairs[1] + stairs[3] 또는 stairs[2] + stairs[3]가 될 수 있다.

그럼 dp[n]인 경우 점화식은 dp[n-3] + stairs[n-1] + stairs[n] (n-3을 밞고 있는 경우 중 최대 + n-2계단 뛰어넘고 n-1, n-2 계단 연속으로 밞기) 또는 dp[n-2] + stairs[n] (n-2 계단 밞는 경우 중 최대 + n-1 뛰어넘고 n밞기) 둘 중 하나가 된다.

bottom up 방식

#include <bits/stdc++.h>
using namespace std;

int n;
int dp[301];
int stairs[301];



int main() {
    cin >> n;
    memset(dp, 0, sizeof(dp));
    for (int i = 1;i < n + 1;i++) { // i == 0 일때는 시작점
        cin >> stairs[i];
    }
    dp[1] = stairs[1];
    dp[2] = stairs[1] + stairs[2];
    for (int i = 3;i <= n;i++) {
        dp[i] = max(dp[i - 2] + stairs[i], dp[i-3] + stairs[i-1] + stairs[i]);
    }
    cout << dp[n];
    return 0;
}

top down 방식

#include <bits/stdc++.h>
using namespace std;

int n;
int dp[301];
int stairs[301];


int solve(int x) {
    if (dp[x] == -1)
        dp[x] = max(solve(x - 2) + stairs[x],solve(x - 3) + stairs[x - 1] + stairs[x] );
    return dp[x];
}

int main() {
    cin >> n;
    memset(dp, -1, sizeof(dp));
    for (int i = 1;i < n + 1;i++) { // i == 0 일때는 시작점
        cin >> stairs[i];
    }
    dp[0] = 0;
    dp[1] = stairs[1];
    dp[2] = stairs[1] + stairs[2];
    solve(n);
    cout << dp[n];
    return 0;
}