[Beakjoon/백준] 2579 파이썬

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

 

사용 알고리즘: DP

 

 

- 1번째 계단에 올라가는 법은 1가지 밖에 없음

• dp[1] = stairs[1] 

 

- 2번째 계단에 올라가는 법

• 1번째 계단 -> 2번째 계단 : dp[2] = stairs[1] + stairs[2] -> 무조건 최댓값이 더 큼
• 2번째 계단:  dp[2] = stairs[2]

 

- 3번째 계단에 올라가는 법

• 1번째 계단 -> 3번째 계단: dp[3] = stairs[1] + stairs[3] 
• 2번째 계단 -> 3번째 계단: dp[3] = stairs[2] + stairs[3]

이 경우에는 계단에 부여된 점수에 따라 상황이 달라질 수 있음

-> dp[3] = max(stairs[1] + stairs[3], stairs[2] + stairs[3])

 

 

- 4번째 계단 이상

• i-3번째 계단 -> i-1번째 계단 -> i번째 계단: dp[i] = dp[i-3] + stairs[i-2] + stairs[i]
• i-2번째 계단 -> i번째 계단: dp[i] = dp[i-2] + stairs[i]

이 경우 역시 위와 같이 계단에 부여된 점수에 따라 상황이 달라질 수 있음

-> dp[i] = max(dp[i-3] + stairs[i-2] + stairs[i], dp[i-2] + stairs[i])

 

dp[n] = max(직전칸에서 올라온 경우의 최댓값, 전전칸에서 올라온 경우의 최댓값)

 

※ 직전칸에서 올라온 경우 최대 값이 dp[i-1] + stairs[i] 가 아닌 이유

dp[i-1] 은 i-1번째 계단에 올랐을 때 얻을 수 있는 최댓값으로 stair[i] + stairs[i-1] + stair[i-2] 의 경우도 포함되어 있기 때문

(세 계단을 연달아 오를 수 없음, 룰 위반)

 

import sys

n = int(sys.stdin.readline())

# 1번째 인덱스부터 사용
stairs = [0] * 301
for i in range(1, n+1):
    stairs[i] = int(sys.stdin.readline())

# n 번째 계단에 올랐을 때 얻을 수 있는 점수 누적 최댓값
dp = [0] * 301
dp[1] = stairs[1]
dp[2] = stairs[1] + stairs[2]
dp[3] = max(stairs[1] + stairs[3], stairs[2] + stairs[3])

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

print(dp[n])