c언어 2579번 계단 오르기 (백준)

#include <stdio.h>
#define max(a, b) ((a>b) ? a : b)

int a[302] = {0};
int dp[302] = {0};

int f(int k) //동적 계획법 
{ //점화식 : n=0부터, n>=4 : dp[n] = a[n] + max(dp[n-2], (dp[n-3] + a[n-1]));
    if(dp[k] > 0) return dp[k];
    
    if(k==0) {
        dp[0] = a[0];
        return dp[0];
    } else if(k==1) {
        dp[1] = a[0] + a[1];
        return dp[1];
    } else if(k==2) {
        dp[2] = a[2] + max(a[0], a[1]);
        return dp[2];
    } else if(k==3) {
        dp[3] = a[3] + max(a[1], a[2]) + a[0];
        return dp[3];
    } else {
        dp[k] = a[k] + max(f(k-2), (f(k-3) + a[k-1]));
        return dp[k];
    }
}

int main(void)
{
    int n = 0;
    scanf("%d", &n);
    
    for(int i = 0; i<n; i++) 
        scanf("%d", &a[i]);
       
    f(n-1);
    
    printf("%d", dp[n-1]);
    return 0;
}

 

 

풀이

특정 층에서의 최댓값을 dp에 저장했다.

 

0부터 시작한다고 하면...

0) dp[0] = a[0]

1) dp[1] = a[1] + a[0]

2) dp[2] = a[2] + max(a[0], a[1])

3) dp[3] = a[3] + max(a[1], a[2]) + a[0]

이다.

 

4)의 경우는

 

0   1   2   3  4              0   1   2   3  4 

O  O  X  O  O             dp[1]  X  O  O

O  X  O  X  O  ------>  dp[2]       X  O

X  O  O  X  O

 

이렇게 세 가지 경우로 볼 수 있으나, 두 개로 줄일 수 있다.

4) dp[4] = a[4] + max(dp[2], (dp[1] + a[3]))

 

5)의 경우는

0   1   2   3   4   5              0   1   2   3   4   5  

O  X  O   O  X  O              dp[3]            X  O

O  O  X   O  X  O ------->  

X  O  O   X  O  O              dp[2]       X  O  O

O  X  O   X  O  O

전처럼 두 개로 나타 낼 수 있다.

5) dp[5] = a[5] + max(dp[3], (dp[2] + a[4]))

 

4), 5)을 보면 n>=4일 때의 점화식을 구할 수 있다.

(n 0부터) n>=4, dp[n] = a[n] + max(dp[n-2], (dp[n-3] + a[n-1]))

 

이 점화식을 이용하여, dp로 풀면 된다

 

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기