Beakjoon 2579 계단 오르기

16 Feb 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/2579

나의 풀이

DP[i] = i번째 계단에서 가장 큰 합 이라고 하고, i번째 계단의 점수를 score[i]라고 할 때 계단은 한 번에 한 계단 또는 두 계단씩 오를 수 있기 때문에 다음과 같이 표현할 수 있다.
DP[i] = max(DP[i-1], DP[i-2]) + score[i]
하지만 이 경우 연속된 세 개의 계단을 모두 밟아서는 안 된다는 조건을 만족시킬 수 없기 때문에 DP를 다시 정의해야 한다.

i번째 계단에서의 합을 두 가지 종류로 분류해보자 첫 번째로는 바로 직전에 있는 이전 계단에서 현재 계단으로 올라오는 경우와 두 번째로 두 칸 전의 계단에서 현재 계단으로 올라오는 경우가 있을 것이다. 이를 각각 정의하면 다음과 같다.
DP[i][0] = i-1번째 계단에서 i번 계단으로 올라왔을 때의 최대 합
DP[i][1] = i-2번째 계단에서 i번 계단으로 올라왔을 때의 최대 합

먼저 DP[i][0]은 i-1번 계단과 i번 계단으로 이미 연속 2번 계단을 밟게 된다는 것을 의미한고. 마찬가지로 DP[i-1][0]은 i-2번, i-1번 계단을 연속으로 밟은 것이므로 DP[i-1][0] 다음으로 추가 될 수 없다. 하지만 DP[i-1][1]은 계단을 연속으로 밟은 것이 아니므로 DP[i][0]에 추가할 수 있다. 결론적으로 DP[i][0]의 값은 다음과 같이 정의된다.
DP[i][0] = DP[i-1][1] + score[i]

반면 DP[i][1]은 i-2번째 계단에서 올라오는 것이므로 연속된 계단이 될 수 없어 다음과 같이 정의된다.
DP[i][1] = max(DP[i-2][0], DP[i-2][1]) + score[i]

최종적으로 계단 꼭대기 N에서 얻을 수 있는 최대 점수는 DP[N][0]과 DP[N][1] 중 더 큰 값이 된다.

풀이 코드 : 2579 계단 오르기

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int DP[301][2];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    vector<int> score;
    int N;
    cin>>N;
    score.resize(N+1);
    for(int i=1;i<=N;i++){
        cin>>score[i];
    }

    DP[0][0] = 0;
    DP[0][1] = 0;
    for(int i=1;i<=N;i++){
        if(i >= 2){
            DP[i][1] = max(DP[i-2][1],DP[i-2][0]) + score[i];
        }else{
            DP[i][1] = score[i];
        }
        DP[i][0] = DP[i-1][1] + score[i];
    }
    
    cout<<max(DP[N][0], DP[N][1]);
}

채점결과