[BOJ] 백준 2579번 - 계단 오르기 (Python)

문제

문제 바로가기

해결

일단 계단의 최대 점수를 계산하는 것이 정형화된 전체 코드로 구현을 할 수 없겠다는 생각이 든다. 하지만 낮은 계단 부터 차근차근 최대 점수를 계산해나가는 바텀업 방식의 다이나믹 프로그래밍 기법을 사용하면 쉽게 풀 수 있을 것 같다는 생각이 든다.

우선적으로 점화식을 한 번 생각해보자.

i번째 계단의 최대 점수 d[i]는 i-1번째 계단 혹은 i-2번째 계단의 점수의 최댓값, 즉 d[i-1] 혹은 d[i-2]에 현재 계단의 점수 s[i] 를 더한 것이다.

즉 점화식으로 나타내면

d[i] = max(d[i-1], d[i-2]) + s[i]일 것이다.

하지만 이때 세 개의 계단을 모두 밟아서는 안된다라는 제약이 있으므로, i번째 계단의 최대 점수 d[i]는 i-3번째 계단의 최대 점수 + i-1번째 계단의 점수와 i-2번째 계단의 최대점수 중 큰 점수에 현재 계단의 점수 s[i]를 더한 값이 될 것이다.

즉 쉽게 말하면, 2칸 점프 후 1칸 점프 + 현재 점수 와 어떻게든 점프 후 2칸 점프 + 현재 점수 중 하나를 비교하는 것이다 !!

그렇다면 위의 점화식은 제약에 의해 다음과 같이 수정될 것이다.

d[i] = max(d[i - 3] + s[i - 1], d[i - 2]) + s[i]

이를 코드로 한 번 작성해보자.

import sys

input = sys.stdin.readline

n = int(input())
s = [0] * 301
d = [0] * 301

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

for i in range(1, n + 1):
  if i == 1:
    d[i] = s[i]
  if i == 2:
    d[i] = d[i - 1] + s[i]
  else:
    d[i] = max(d[i - 3]+s[i - 1], d[i - 2]) + s[i]

print(d[n])