[백준] 2579. 계단오르기 / python 파이썬

🚩 DP

 

thinking

전형적인 DP 문제이다.

무조건 마지막 계단을 밟아야 하므로 리스트를 뒤집어 0번 인덱스부터 시작해줬다.

연속된 세 개의 계단을 밟으면 안되기 때문에 dp[i-1]+s[i] 로 하지 않고 dp[i-3]+s[i-1]+s[i] 로 설정해줬다.

 

런타임에러 (IndexError) 주의 !

첫계단과 두번째 계단을 아래처럼 설정했더니 인덱스 에러가 났다. range의 범위가 3 이하일 수 있으므로 패쓰코드처럼 작성해야 한다.

# Index Error 난 부분
dp = [0]*N
dp[0] = s[0]
dp[1] = s[0]+s[1]
dp[2] = s[0]+s[2]

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

 

코드

N = int(input())
s = [int(input()) for _ in range(N)]
s.reverse()

dp = [0]*N
dp[0] = s[0]

for i in range(1, N):
    if i < 3:
        dp[i] = s[0] + s[i]
    else:
        dp[i] = max(dp[i-2]+s[i], dp[i-3]+s[i-1]+s[i])

print(max(dp[N-2], dp[N-1]))