2579: 계단 오르기 - Python

문제

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

풀이1 (오답: IndexError)

import sys
input = sys.stdin.readline

n = int(input())  # n == 1 or n == 2인 경우
steps = [0] * (n+1)
dp = [0] * (n+1)

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

dp[1] = steps[1]
dp[2] = steps[1] + steps[2]
dp[3] = max(steps[1], steps[2]) + steps[3] # IndexError 발생

for i in range(4, n+1):
    dp[i] = max(dp[i-3] + steps[i-1], dp[i-2]) + steps[i]

print(dp[n])

• 테스트 케이스는 맞았는데 채점 시 IndexError가 발생하는 경우, 대부분 입력 조건을 제대로 검증하지 않은 탓이다.
• 위 코드에서는 n==1 or n==2일 때, dp[3]은 정의되지 않으므로 IndexError가 발생한다.

풀이2 (정답)

import sys
input = sys.stdin.readline

n = int(input())
steps = [0] * 301 # IndexError 해결
dp = [0] * 301

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

dp[1] = steps[1]
dp[2] = steps[1] + steps[2]
dp[3] = max(steps[1], steps[2]) + steps[3]

for i in range(4, n+1):
    dp[i] = max(dp[i-3] + steps[i-1], dp[i-2]) + steps[i]

print(dp[n])

매번 1칸이나 2칸씩 오를 수 있으며, 연속된 3칸에 오를 수 없다는 문제 조건에 주목하면,
k번째 계단에 오르기 위해선 다음 2가지 case가 존재한다.

1. 2칸 전의 계단(k-2)에서 올라오는 경우: dp[k-2] + steps[k]
2. 1칸 전의 계단(k-1)에서 올라오는 경우: dp[k-3] + steps[k-1] + steps[k]