[백준][2579번][DP] 계단 오르기

계단 오르기

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

<코드>

#include <stdio.h>
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int main(void){
    
    int N;
    int stair[305] = {};
    int Dp[305] = {};
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++)
        scanf("%d", &stair[i]);
 
    for (int i = 1; i <= 3 && i <= N; i++)
        if (i!=3)
            Dp[i] = Dp[i - 1] + stair[i];
        else
            Dp[i] = max(stair[i] + Dp[i - 2], stair[i] + stair[i - 1]);
 
    for (int i = 4; i <= N; i++)
        Dp[i]=max(stair[i] + Dp[i - 2], stair[i] + stair[i - 1] + Dp[i - 3]);
 
    printf("%d\n", Dp[N]);
 
}

<문제 푼 요령>

1. 이 문제는 계단을 오르는건데 조건이 3개 연속으로 밟을 수 없는 경우다. 즉 현재의 계단에 올 수 있는 경우의 수는 두가지다.

2. 첫번째로 현재 있는 계단 전의 계단을 밟지 않는 경우와 현재 있는 계단 전의 계단을 밟은 경우 이렇게 두가지로 나올 수 있다.

3. 즉 Dp[i]=max(stair[i] + Dp[i - 2], stair[i] + stair[i - 1] + Dp[i - 3]) 값을 계속 비교해나가면서 더하면 N 번째에 원하는 정답을 구할 수 있다.