2579번

2579번 - 계단 오르기

D[N] = N번째 계단을 오르는 최대 값

N번째 계단을 오르는 방법은 조건에 따라 두가지가 된다.

1. N-2칸에서 2칸 점프하여 오르는 경우.

2. N-1칸에서 1칸 점프하여 오르는 경우.

하지만 2번째 경우일 때는 문제의 조건에 따라 연속된 3칸을 밟으면 안되므로

N-3칸에서 N-1칸으로 2칸 점프한후, N-1칸에서 N칸으로 1칸 점프해야 한다.

(N-2칸에서 N-1칸으로 1칸 점프한후, N-1칸에서 N칸으로 1칸 점프하는 경우 조건에 위배된다.)

따라서 D[N] = max(D[N-2]+stair[N] , D[N-3] + stair[N-1] + stair[N]) 이라는 점화식이 완성된다.

1달 전에 혼자 풀었을 때는 2차원 DP로 풀었는데 다시 풀어보니 그럴 필요까진 없었던 문제였다.

<정답 코드>

#include<iostream>
#include<algorithm>
using namespace std;
 
int N;
int stair[301];
int D[301];
int ans;
int go(int n)
{
    
    if(n<=0)
    {
        return 0;
    }
    if(n==1)
    {
        return stair[n];
    }
    if(D[n]!=0)
    {
        return D[n];
    }
   
    
    D[n]=max(go(n-2)+stair[n],go(n-3)+stair[n-1]+stair[n]);
    
    return D[n];
    
    
    
}
int main()
{
    cin>>N;
    for(int i=0;i<301;i++)
    {
        D[i]=0;
    }
    for(int i=1;i<=N;i++)
    {
        cin>>stair[i];
    }
    
    cout<<go(N)<<endl;
    return 0;
}

<완전 탐색 코드 - 9%에서 시간 초과>

#include<iostream>
#include<algorithm>
using namespace std;
 
int N;
int stair[301];
int ans;
void go(int n,int sum)
{
    
    if(n<=0)
    {
        return;
    }
    if(n==1)
    {
        return ;
    }
    
    ans=max(ans,sum);
    
    go(n-2,sum+stair[n]);
    go(n-3,sum+stair[n]+stair[n-1]);
    
    return;
    
    
    
}
int main()
{
    cin>>N;
    for(int i=1;i<=N;i++)
    {
        cin>>stair[i];
    }
    
    go(N,0);
    
    cout<<ans<<endl;
    return 0;
}