백준_python 2579번 계단 오르기 (DP)

<문제 링크>

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

 

 

<정답 코드>

import sys
input = sys.stdin.readline
 
n = int(input())
 
stairs = [0] * 301
for i in range(1, n + 1):
    stairs[i] = int(input())
 
if n == 1:
    print(stairs[1])
    exit(0)
 
elif n == 2:
    print(stairs[1] + stairs[2])
    exit(0)
 
 
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])
 
print(dp[n])

 

각 상황마다 최대값을 선택하여 dp 배열에 추가하는 식으로 진행하면 마지막에 가능한 최대 점수를 얻을 수 있다. 

 

세 개의 계단을 연속해서 밟은 수 없다는 조건을 만족하기 위해,

현재 계단에 올 수 있는 경우의 수를 두 가지로 나누어서 고려하는 것이다.

 

현재 계단(i)에 오기 위해,

(현재 계단 기준)

1) 직전 계단(i-1)과 세번째 전 계단(i-3)을 밟는 것

2) 두 번째 전 계단(i-2)을 밟는 것

위 두 가지의 방법이 있다.

 

DP 공부를 얼른 해야겠다.