[BaekJoon] 2579 계단 오르기 - Python 풀이

문제 

난이도

Silver 3

입력 조건

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300 이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000 이하의 자연수이다.

 

 

출력 조건

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

입력 예시 

6
10
20
15
25
10
20

 

출력 예시 

75

처음 짠 코드

import sys
n = int(input())
scores = [int(sys.stdin.readline()) for _ in range(n)]

d = [0] * (n+1) # index번째 계단까지에 오를 수 있는 최댓값을 담고 있는 DP 테이블

if n>=1:
    d[1] = scores[0]
if n>=2:
    d[2] = scores[0] + scores[1]
if n>=3:
    for i in range(3,n+1):
        d[i] = max(d[i-2]+scores[i-1], d[i-3]+scores[i-2]+scores[i-1]) 
print(d[n])

 

느낀 점

연속으로 3개의 계단을 밟지 못한다는 조건 때문에 점화식을 짤 때 굉장히 애를 먹었다..

결국 문제 풀이 아이디어는 다음과 같다.

1. 현재 위치 i를 기준으로 i-2번째까지의 최댓값을 구하고 현재 score를 더한다.
2. 현재 위치 i를 기준으로 i-3번째까지의 최댓값을 구하고 현재 score와 i-1번째 score를 더한다.

1번은 연속되지 않은 경우이고,

2번은 연속된 경우이다.

이렇게 두 가지를 놓고 더 큰 값을 택하는 식으로 점화식을 구성하면 된다.