[백준] 2579번

이 문제는 동적계획법으로 푸는 문제인데 아직 동적계획법에 대한 이해가 조금 부족한게 느껴진다. 일단 여러 경우의수에 대해서 생각은 하는데 코드로 구현하는게 조금 어려운거 같다. 언제 원래의 값을 더해야하고 언제 dp에 넣어놓은 값을 더해야하는지 헷갈리는 것 같다. 이 역시 문제를 풀다보면 이해가 될 거라고 생각한다. 아직은 어렵다 동적계획법은! 그렇지만 앞으로 더 풀어지면서 익숙해지리라 믿는다.

 

#include <iostream>
using namespace std;

int max(int num, int num1){
    if(num>num1)
        return num;
    return num1;
}
int main(){
    int numofstairs;
    cin>>numofstairs;
    int *stairs=new int[numofstairs+1];
    int *dp=new int[numofstairs+1];
    int i;

    for(i=1;i<=numofstairs;i++){
        cin>>stairs[i];
    }
    dp[1]=stairs[1];
    dp[2]=max(stairs[2]+stairs[1],stairs[2]);
    dp[3]=max(stairs[1]+stairs[3],stairs[2]+stairs[3]);
    

    for(i=4;i<=numofstairs;i++){
        dp[i]=max(dp[i-3]+stairs[i]+stairs[i-1],dp[i-2]+stairs[i]);
    }

    cout<<dp[numofstairs]<<endl;

}