[백준] 2579번 문제 (계단 오르기) 파이썬(Python) 풀이

n = int(input())
steps = [0 for i in range(301)]

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

dp = [steps[0]] + [0 for i in range(300)]
dp[1] = steps[0] + steps[1]
dp[2] = max(steps[1] + steps[2], steps[0] + steps[2])

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

print(dp[n - 1])

dp에 해당 계단을 밟았을 때 최대의 점수를 저장한다고 생각하고 풀면 좀 더 쉽게 접근할 수 있을 것 같다.

아래 dp를 순회하는 for문에서 적용된 식인 dp[i] = max(dp[i - 3] + steps[i - 1] + steps[i], dp[i - 2] + steps[i]) 는

 

dp[i - 3] + steps[i - 1] + steps[i] 와

dp[i - 2] + steps[i] 중에 더 큰 값을 dp에 저장한다.

 

이 두 개의 식이 만들어진 이유는 문제의 3번 규칙으로부터 시작된다.

마지막 도착 계단은 무조건 밟는다고 했으니,

 

1. 마지막 계단을 밟으면서 그 전 계단을 밟는 경우.

2. 마지막 계단을 밟으면서 그 전 계단을 밟지 않는 경우.

 

위와 같이 두 개의 경우가 나오고 해당 경우의 수는 순서대로

 

1. dp[i - 3] + steps[i - 1] + steps[i]

2. dp[i - 2] + steps[i]

 

로 나타낼 수 있다.