백준 계단 오르기 코드 및 해설 (파이썬)

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

2579번: 계단 오르기

 

다이나믹 프로그래밍 문제..

점화식 세우는 게 너무 어렵다 

dp[i] = max(dp[i-2]+scores[i], dp[i-3]+scores[i-1]+scores[i])

이게 아니라 

dp[i] = max(dp[i-2]+scores[i], dp[i-3]+scores[i-1]+scores[i], dp[i-1]) 가 아닌가?! 하는 오해가 있었는데

(불리하면 현재 계단을 밟지 말아야 한다고 생각해서)

한 번에 2개 이상의 계단을 뛰어넘을 수 없어서 위의 점화식이 맞다고 한다..

 

import sys
N = int(sys.stdin.readline())
scores = []
for _ in range(N):
	scores.append(int(sys.stdin.readline()))

if N < 3:
	print(sum(scores))
else:
	dp = [0] * N
	dp[0] = scores[0]
	dp[1] = scores[0] + scores[1]
	dp[2] = max(scores[0]+scores[2], scores[1]+scores[2])

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

	print(dp[-1])