백준 알고리즘 2579번 - 계단 오르기

대표적인 dp문제라고 할 수 있다.

 나는 dp[계단 위치][바로 전에 올라간 칸수] 배열을 선언했다.

또 마지막 칸은 무조건 밟기 때문에 계단을 뒤집어서 맨 마지막 칸을 맨 처음 칸으로 바꿔서 계산하자.(이렇게 풀어야 예외처리 필요없이 일관성있는 코드가 될 것같다)

 

이렇게 분할하면 바로 전에 1칸 올라간 경우, 2칸 올라간 경우를 따로 계산해 주어야 한다.

이때 생각 해주어야 하는 게 있는데,

한 칸 올라간 경우에는 바로 전에 올라간 계단 수가 무조건 두 칸이여야 하고

두 칸 올라간 경우에는 바로 전에 올라간 계단의 수가 상관없다.

 

점화식으로 나타내면 ,

dp[i][2]=max(dp[i-2][2],dp[i-2][1])+arr[i]

dp[i][1]=dp[i-1][2])+arr[i]

 

주의 해야할 것은 마지막 계단을 출력하는게 아닌,

dp[마지막][1], dp[마지막][2] , dp[마지막-1][1], dp[마지막-1][2] 중 가장 큰 걸 출력해야한다

(처음에 두칸을 뛸 수도 있고 한 칸을 뛸 수도 있기 때문)

 

소스코드

 

// Example program
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main()
 
{
    int arr[301];
    int dp[301][3]={0,};
    int n; 
    int ans=0;
    cin>>n;
    
    //배열을 입력한다 
    /*
    마지막 계단을 무조건 밟으므로 배열을 뒤집자
    */
    for(int i=1;i<=n;i++) cin>>arr[n-i+1];
    
    //초기값 지정
    dp[2][1]=arr[1]+arr[2];
    dp[3][2]=arr[1]+arr[3];
    
    //memoization
    /*
    점화식 dp[i][2]=max(dp[i-2][2],dp[i-2][1])+arr[i]
           dp[i][1]=dp[i-1][2]+arr[i]
    
    */
    for(int i=4;i<=n;i++){
        dp[i][1]=dp[i-1][2]+arr[i];
        dp[i][2]=max(dp[i-2][2],dp[i-2][1])+arr[i];
    }
    
    //마지막 위치가 맨 처음 계단 일 수도 있고, 2번째 계단 일 수도 있다. 
    //처음에 2칸을 뛸 수도 있기 때문
    for(int i=n-1;i<=n;i++){
        for(int j=1;j<=2;j++)
            if(ans<dp[i][j]) ans=dp[i][j];
    }
    cout<<ans;
}