/<> 백준 2579번 : 계단 오르기 (C언어)

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

 

 

DP를 통해 문제를 풀어나갑니다. 그러기 위해선 규칙을 찾아야 하는데, 늘 DP 문제는 규칙을 찾는게 일인 것 같습니다.

연속으로 2번까지만 오를 수 있고, 두 칸을 오르는 것은 언제든 가능합니다. 그럼 n번째 계단까지 올랐을 때의 점수는 다음 두 가지가 나옵니다.

 

1. stair[n] + stair[n - 1] + stair[n - 3] : 계단을 연속으로 오르는 경우, i - 3번째 계단을 더하는 이유는 연속으로 한 칸 씩 올랐다는 점을 구분짓기 위함!

 

2. star[n] + stait[n - 2] : 계단을 두 칸 오르는 경우

 

위의 규칙을 이용하여 DP 방식으로 문제를 풀어나가면 됩니다.

 

 

<코드>

#include <stdio.h>

int n;
int stair[301];
int dp[301];

int big(int a, int b) {
    return a > b ? a : b;
}

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &stair[i]);
    
    dp[0] = stair[0];
    if (n > 1) dp[1] = stair[0] + stair[1];
    if (n > 2) dp[2] = big(stair[1] + stair[2], stair[0] + stair[2]);

    for(int i = 3; i < n; i++) {
        dp[i] = big(dp[i-3] + stair[i-1] + stair[i], dp[i-2] + stair[i]);
    }

    printf("%d\n", dp[n - 1]);
    return 0;
}

 

 

 

계단을 오르는 방식을 구할 때 점화식 규칙을 찾는 느낌이 들었습니다. DP는 수학과 밀접한 알고리즘인 것 같습니다.