[BaekJoon] 2579번 : 계단 오르기

• 이 글은 c++로 풀이를 작성하였습니다.

문제

 

예시

 

풀이

• DP를 활용하여 해결해야 하는 문제입니다.
• 기존의 DP는 1차원 점화식을 사용했다면, 이번 문제는 2차원배열을 이용한 점화식을 구해야 합니다. (연속적으로 3개의 계단을 밟는지에 대한 판단 때문에)
• D[i][1] : i번째 계단까지 포함하여 연속된 계단 수가 1인 경우, 즉 D[i-1]은 밟지 않고, D[i-2]를 밟은 경우
• D[i][2] : i번째 계단까지 포함하여 연속된 계단 수가 2인 경우, 즉 D[i-1]을 밟고 D[i]를 연속적으로 밟은 경우
• 따라서 D[num][1]과 D[num][2] 중에 최댓값이 답이 됩니다.

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


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int vec[350];
    int num;
    cin>>num;
    vec[0] = 0;
    
    for(int i=1;i<=num;i++){
        cin>>vec[i];
    }
    int d[350][3];
    
    d[0][1] = 0;
    d[0][2] = 0;
    d[1][1] = vec[1];
    d[1][2] = 0;
    
    for(int i=2;i<=num;i++){
        d[i][1] = max(d[i-2][1] , d[i-2][2])+vec[i];
        d[i][2] = d[i-1][1] + vec[i];
    }
    
    int result = d[num][1]>d[num][2]?d[num][1]:d[num][2];
    cout<<result;
}

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.