백준 2579 계단 오르기

haruponea·2021년 4월 4일
0

BOJ

목록 보기
34/41

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

풀이
dp문제였습니다. 계단을 연속으로 3칸이상 오를 수 없다는 조건을 잘 처리해야했습니다. dp[i]는 i번째 계단을 반드시 밟았을 때 점수의 최댓값을 저장합니다.
점화식은 다음과 같습니다.
dp[i] = max(dp[i-3] + stair[i-1] + stair[i], dp[i-2]) + stair[i]
i번째 칸을 연속해서 2칸밟거나 연속하지않고(i-1번째 칸을 밟지 않고) 밟는 경우 중 최댓값을 구하면 됩니다. 연속해서 2칸을 밟을 경우 i-2번째 칸을 밟지 않아야하기 때문에 dp[i-3]에 i-1, i 번째 칸을 더해주면 됩니다. 연속하지 않고 밟을 경우 i-1번째만 안밟으면 되기 때문에 dp[i-2]에 i번째 칸을 더해주면 됩니다.

Python

import sys
input = sys.stdin.readline
n = int(input())
stair = [0]*303
for i in range(1, n + 1):
    stair[i] = int(input())
dp = [0]*303
dp[1], dp[2], dp[3] = stair[1], stair[1] + stair[2], max(stair[1], stair[2]) + stair[3]
for i in range(4, n + 1):
    dp[i] = max(dp[i-3] + stair[i-1], dp[i-2]) + stair[i]
print(dp[n])

0개의 댓글