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

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

풀이

이 문제는 i번째 계단에서의 점수가 i-1번째 계단을 밟는지 여부에 영향을 받으므로 DP를 이용해서 풀었다.

dp[i][j] 라는 배열에 아래 상황일 때의 최대 점수를 저장한다.

• i번째 계단을 밟았음
• j+1개의 계단을 연속으로 밟았음

j=0일 때, i-1번째 계단을 밟지 않고 i번째 계단을 밟았으므로 i-2번째 계단을 밟은 것이다.
j=1일 때, i-1번째 계단을 밟고 i번째 계단을 밟았으므로 i-2번째 계단을 밟지 않은 것이다.

• dp[i][0] = max(dp[i-2][0], dp[i-2][1]) + step[i]
• dp[i][1] = dp[i-1][0] + step[i]

따라서 총 점수의 최댓값은 max(dp[n][0], dp[n][1])이다.

코드

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;
    
    vector<int> step(n+1, 0);
    vector<vector<int>> dp(n+1, vector<int> (2, 0));
    
    for(int i=1; i<=n; i++){
        cin >> step[i];
    }
    
    dp[1][0] = step[1];
    for(int i=2; i<=n; i++){
        dp[i][0] = max(dp[i-2][0], dp[i-2][1]) + step[i];
        dp[i][1] = dp[i-1][0] + step[i];
    }
    
    cout << max(dp[n][0], dp[n][1]);

    return 0;
}