2579번: 계단 오르기(70분)

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

구현 아이디어 60분 구현 10분

풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int Dp[301][2];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("input.txt", "rt", stdin);

    int N{};
    cin >> N;

    vector<int> Score(N);
    for (int i = 0; i < N; ++i)
    {
        cin >> Score[i];
    }

    // Dp[i][0]: 그 전 것 밟음, Dp[i][1]: 그 전전 것 밟음
    Dp[0][0] = Score[0];
    Dp[0][1] = Score[0];

    Dp[1][0] = Score[0] + Score[1];
    Dp[1][1] = Score[1];

    // 마지막 도착 계단은 반드시 밟아야 한다. 
    // Dp 배열에는 i 번째 계단을 밟는 경우의 최댓값을 넣는다.
    for (int i = 2; i < N; ++i)
    {
        // i 번째 계단을 밟을 경우.
        // i-1 번째 계단을 밟는다면, i-2 번째 계단은 밟을 수 없기 때문에 Dp[i-1][1]을 더한다.
        Dp[i][0] = Score[i] + Dp[i - 1][1];

        // i-1 번째 계단을 밟지 않는다면, i-2 번째 계단의 0 번째 값, 1 번째 값 중 최댓값을 더한다.
        Dp[i][1] = Score[i] + max(Dp[i - 2][0], Dp[i - 2][1]);
    }

    cout << max(Dp[N - 1][0], Dp[N - 1][1]);

    return 0;
}