[BOJ / 파이썬] 2579: 계단 오르기

백준 / BOJ / Python / 파이썬

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

2579번: 계단 오르기

단계 : 동적 계획법 1

알고리즘 분류 : 다이나믹 프로그래밍

 

풀이:

계단에 각각의 점수가 적혀져 있으며 시작점(시작점은 계단이 아님)부터 계단을 올라 마지막 계단까지 올랐을 때 점수가 가장 높게 계단을 오르는 법을 구하는 문제이다. 계단은 한번에 한 계단씩 혹은 두 계단씩 오를 수 있으며 연속된 3개의 계단을 밟을 수는 없다.

 

이런 류의 문제는 해당 계단을 밟았을 때 최댓값이 얼마인지?를 기준으로 답을 구해나가야 한다.

아래 코드에서는 ls에 각 계단의 점수를 저장하고 dp에 위에서 말한 n번째 계단을 밟았을 때의 최댓값을 저장할 것이다.

즉 ls[0]은 첫번째 계단의 점수를 가지고 있고 dp[0]은 첫번째 계단에 도착했을 때 점수의 최댓값을 저장한다.

 

첫번째 계단은 당연히 첫번째 계단의 점수가 최댓값 그 자체이고

두번째 계단 역시 첫번째 계단을 거쳐 두번째 계단을 밟은 것이 최댓값이다.

세번째 계단은 연속으로 세개의 계단을 밟으면 안된다는 조건이 있으므로 [시작점 -> 1계단 -> 3계단] 경로와 [시작점 -> 2계단 -> 3계단] 경로 중 큰 값이 도착했을 때 최댓값이다.

 

n번째 계단 역시 연속으로 된 세개의 계단을 밟으면 안된다는 조건을 신경써야 한다.

모든 계단은 두가지 경우의 수가 있는데 두개 전 계단에서 올라왔을 때와 한개 전 계단에서 올라왔을 때이다.

n에 대해 dp의 점화식을 생각해보면 두개 전 계단에서 올라왔을 때[n-2번째 계단까지의 최댓값 + n번째 계단의 값], 한개 전 계단에서 올라왔을 때[n-3번째 계단까지의 최댓값 + n-1번째 계단의 값 + n번째 계단의 값] 중 최댓값을 찾으면 된다.

 

두개 전 계단에서 올라왔을 때는 한개 전 계단을 밟은 것이 아니기 때문에 애초에 연속 계단 조건을 생각할 필요가 없다.

한개 전 계단에서 올라왔을 때를 생각하려면 연속 계단 조건 때문에 필수적으로 두개 전 계단을 밟으면 안된다. 그러므로 꼭 [세개 전 계단 -> 한개 전 계단 -> 이번 계단]의 루트를 밟아야 하는데 이때 세개 전 계단까지는 어떤 방법으로 올라왔든 이번 계단의 연속 계단 조건에 영향을 주지 않는다. 

 

이렇게 구한 점화식을 기준으로 코드를 작성하면 마지막 계단을 밟았을 때 점수의 최댓값을 구할 수 있다.

코드

import sys

n = int(sys.stdin.readline())
ls = [0 for _ in range(300)]
dp = []
for i in range(n):
    ls[i] = int(sys.stdin.readline())

dp.append(ls[0]) # 1계단 도착 최댓값
dp.append(ls[0] + ls[1]) # 2계단 도착 최댓값
dp.append(max(ls[0] + ls[2], ls[1] + ls[2])) # 3계단 도착 최댓값

for i in range(3, n):
    dp.append(max(dp[i - 2] + ls[i], dp[i - 3] + ls[i - 1] + ls[i])) # n계단 도착 최댓값

print(dp[n - 1])