[백준/C/Python] 2579 - 계단 오르기

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

---

구현 과정

DP

각 계단에서의 점수가 이전에 어떤 계단을 밟았는지에 따라 결정되기 때문에 dp를 이용해 푸는 것이 적절하다.

문제에서 연속으로 3개의 계단을 밟을 수 없다고 되어 있다.

예를 들면 4번째 계단에서의 점수 최댓값 (dp[4])을 구하는 경우,

1. 2번째 계단 -> 4번째 계단으로 갈건지 (3번째 계단을 건너뛸건지)
2. 1번째 계단 -> 3번째 계단 -> 4번째 계단으로 갈건지 (2번째 계단을 건너뛸건지)

를 선택해야 된다.

이를 정리해보자면, 각 단계에서 아래 두 케이스의 점수 중 max를 찾아 dp[i]에 저장해야 한다.

1. i-1 번째 계단을 건너뛰는 경우
2. i-2 번째 계단을 건너뛰는 경우

dp[0], dp[1], dp[2]의 경우는 해당 규칙을 따를 필요가 없으므로 먼저 초기화해준다.
dp[3]부터는 for문을 이용해 값을 찾는데,

• 위에서의 케이스 1 - dp[i - 2] + score[i]
• 위에서의 케이스 2 - dp[i - 3] + score[i - 1] + score[i]

로 나타낼 수 있으므로 이 둘의 max를 찾아 dp[i]에 저장한다.

---

전체 코드

C

#include <stdio.h>
#include <stdlib.h>

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

int main() {
    int n;
    scanf("%d", &n);

    int *score = (int *)malloc(sizeof(int) * n + 1);
    int *dp = (int *)malloc(sizeof(int) * n + 1);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &score[i]);
    }

    dp[0] = 0;
    dp[1] = score[1];
    if (n >= 2)
        dp[2] = score[1] + score[2];

    for (int i = 3; i <= n; i++)
        dp[i] = max(dp[i - 2] + score[i], dp[i - 3] + score[i - 1] + score[i]);

    printf("%d\n", dp[n]);

    free(score);
    free(dp);
    return 0;
}

Python

def dp(score):
    n = len(score) - 1
    if n == 0:
        return 0
    if n == 1:
        return score[1]
    if n == 2:
        return score[1] + score[2]
    
    dp = [0] * (n + 1)
    dp[1] = score[1]
    dp[2] = score[1] + score[2]
    if n >= 3:
        dp[3] = max(score[1] + score[3], score[2] + score[3])
    
    for i in range(3, n + 1):
        dp[i] = max(dp[i - 2] + score[i], dp[i - 3] + score[i - 1] + score[i])

    return dp[n]


n = int(input())
score = [0] * (n + 1)
for i in range(1, n + 1):
    score[i] = int(input())

print(dp(score))