알고리즘/백준 문제풀이

[boj] 백준 2579 계단 오르기 python 풀이

감자156 2023. 8. 16. 11:37
반응형

문제

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

 

2579번: 계단 오르기

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점

www.acmicpc.net

 

 

문제 풀이

dp, 세번 연속으로 1칸씩 이동하는 경우는 없어야 하므로, dp[i]가 두번째 1칸씩(stairs[i-1] + stairs[i-2]) 이동이라면 dp[i-3]을 더해줘서 무조건 불연속하게 만들기

 

코드

import sys
input = sys.stdin.readline

N = int(input().strip())
stairs = [int(input().strip()) for _ in range(N)]

dp = [0 for _ in range(N)]
dp[0] = stairs[0]
if N > 1:
    dp[1] = stairs[1]+stairs[0]
if N > 2:
    dp[2] = max(stairs[2] + stairs[1], stairs[2] + stairs[0])

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

print(dp[-1])
반응형