길게 쓰려고 쓰는 글은 아니고 그냥 이런 것도 있다 정도 정리해두려고 쓰는 글

먼저 나의 풀이

//계단 오르기 - 실버 3

#include <iostream>
#include <vector>

using namespace std;

void setDp(const vector<int>& arr, vector<vector<int>>& dp, int n) {
    dp[0][0] = arr[0];
    if (n == 1) return;

    dp[1][0] = arr[0] + arr[1];
    dp[1][1] = arr[1];
    if (n == 2) return;

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

int main() {
    int n;
    vector<int> arr;
    vector<vector<int>> dp;
    cin >> n;
    arr.assign(n, 0);
    dp.assign(n, vector<int> (2, 0));

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    setDp(arr, dp, n);
    cout << max(dp[n-1][0], dp[n-1][1]);

}

나는 dp 배열을 한 칸 넘어서 오는 애들, 두 칸 넘어서 오는 애들로 행을 2개로 해서 2차원으로 정의했음

그렇게 한 다음 한 칸 넘어서 오는 애들은 전 칸에서 두 칸 넘어 온 애들 밖에 못 들어 오니까 그렇게 주고, 두 칸은 누구든지 올 수 있으니까 두 값 중 맥스로 넘어서 오는 식으로

최종적으로는 둘 중 더 큰 값을 출력하는 것으로 마무리

근데 이걸 그냥 1차원으로 할 수도 있더라… 다른 사람들 코드 보니까

두 칸 넘어오는 건 똑같은데, 한 칸 올 때 결국 세 칸 뒤 -> 한 칸 뒤 -> 지금 내 칸 이 테크로 넘어온 애들이 와야되는 거잖음?

그니까 그걸 그냥 수동으로 계산해준 다음에 두 칸이랑 max 해서 더 큰 거 넣어주는 식으로 하면 1차원으로도 표현 가능…

아무래도 dp는 메모리를 많이 먹으니까 이렇게 공간 복잡도 줄일 수 있는 방법 알아두면 나중에 좋을 것 같아서 적어둠.

코드로 쓰자면 이럼

dp[i] = max(dp[i-2] + arr[i], dp[i-3] + dp[i-1] + arr[i]);