[BOJ/python] 2579: 계단 오르기

문제

✔️ silver 3
다이나믹 프로그래밍

문제 흐름

이 문제에서 부분 문제는 "현재 계단까지 도달하면서 얻을 수 있는 최대 점수를 구하는 것"이다.
이 문제를 풀기 위해서는 두가지 경우를 비교해 더 큰 점수를 구해야한다.

1. i-1번째 계단을 밟고 i번째 계단에 온 경우
   -> i-1, i번째 계단을 밟으므로 i-2번째 계단은 밟을 수 없다.
2. i-2번째 계단을 밟고 i번째 계단에 온 경우

1.의 경우 i-3 계단에 도착하는 최대 점수에 i-1 계단의 점수, i 계단의 점수를 더해 구할 수 있다.
2.의 경우는 i-2 계단에 도착하는 최대 점수에 i 계단의 점수를 더해 구할 수 있다.
이 두 점수를 계산해 더 큰 점수가 i 계단에 도착하는 최대 점수가 된다.
같은 방식을 반복해서 n번째 계단까지 점수를 구해주면 된다.

초기값은 두가지 설정해줬다.
i-1, i-2번째 계단이 존재하지 않는 1, 2번째 계단의 값을 설정해준다.
각 계단에 도달할 경우의 최대 점수는 max_scores에 저장했다. 참고로 0번째 계단 (값 0)부터 시작했다.

코드

# 계단 오르기
# dp

import sys
input = sys.stdin.readline

def dp (steps: list):
    n = len(steps)
    max_scores = [0 for i in range(n)]
    if n < 3:
        return steps[-1]
    max_scores[0] = steps[0]
    max_scores[1] = steps[1]
    max_scores[2] = steps[1] + steps[2]

    for i in range(3, n):
        score = max(max_scores[i - 2], max_scores[i - 3] + steps[i - 1]) + steps[i]
        max_scores[i] = score
    # print(max_scores)
    return max_scores[-1]


if __name__ == "__main__":
    s = int(input())
    steps = [0]
    for step in range(s):
        score = int(input())
        steps.append(score)
    
    result = dp(steps)
    print(result)

마무리

어떻게 풀어야하는지 고민을 정말 오래헀던 문제
답을 알 것 같은 애매한 느낌만 들어서 gpt한테 힌트만 달라고 부탁했다.
이렇게 푸는 방식도 나쁘지 않았다.
이렇게 점화식(부분 문제)를 생각하는 힘을 길러야만 dp를 잘 풀 수 있을 것 같다.