[Python] 백준 2579 계단 오르기 | DP

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

2579번: 계단 오르기

 

 

문제 해결 포인트

- 최대 300개 계단의 점수를 기록할 배열 미리 선언

- 계단 별 점수 기록 배열과 dp 기록을 저장할 배열 2개 필요

 

- 계단 1 : 본인 점수

   계단 2 : 계단 1 + 본인 점수

   계단 3 : max(계단 1 + 본인 , 계단 2 + 본인)

- 점화식 : max( 본인 이전 계단 밟고 본인 , 본인 이전 계단 밟지 않고 본인)

       a_i  = max( dp[a_i-3] + floor[a_i-1] + floor[a_i] , dp[a_i-2] + floor[a_i])

 

 

작성 코드

import sys
input = sys.stdin.readline

n = int(input())
floor = [0]*301
dp = [0]*301
for i in range(1, n+1):
    floor[i] = int(input())

dp[1] = floor[1]
dp[2] = floor[1] + floor[2]
dp[3] = max(floor[1] + floor[3], floor[2] + floor[3])

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

print(dp[n])

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚

 

---

REFERENCE

https://pacific-ocean.tistory.com/149