문제풀이/DP
[파이썬] [DP] 백준 2579 계단 오르기
승무_
2022. 2. 24. 12:46
문제
https://www.acmicpc.net/problem/2579
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점
www.acmicpc.net
코드
n=int(input())
array=[0]
for _ in range(n):
array.append(int(input()))
if n==1:
print(array[1])
else:
dp=[0]*(n+1)
dp[1]=array[1]
dp[2]=array[1]+array[2]
for i in range(3,n+1):
dp[i]=max(dp[i-3]+array[i-1]+array[i],dp[i-2]+array[i])
print(dp[n])