[BOJ/백준] 2579번 계단 오르기 (Python 파이썬)

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

2579번: 계단 오르기

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

130015

44456

32196

33.991%

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

<그림 1>

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

<그림 2>

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

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

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

출력

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

예제 입력 1

6
10
20
15
25
10
20

예제 출력 1

75

 

---

풀이

Bottom-Up 방식으로 DP를 구현했습니다. 

dp 리스트에는 i번째 계단을 올랐을 때 얻을 수 있는 최대 점수를 담았습니다.

즉, dp에는 각 인덱스마다 항상 최댓값이 담기는 것이 보장됩니다.

편의를 위해 dp 리스트를 0이 아닌 1번부터 시작하도록 구성했습니다.

import sys
input = sys.stdin.readline

n = int(input())
stairs = [0] + [int(input()) for _ in range(n)] + [0]
dp = [0] * (n+2)
dp[1] = stairs[1]
dp[2] = dp[1] + stairs[2]

for i in range(3, n+1):
    # i번쨰 계단을 2칸으로 올라온 경우, 1칸으로 올라온 경우
    dp[i] = max(dp[i-2], dp[i-3] + stairs[i-1]) + stairs[i]
print(dp[n])

dp[1]에는 첫번째 계단까지 올랐을 때의 최대 점수입니다. 이때는 그냥 1칸 오르는 수밖에 없습니다.
dp[2]에는 두번째 계단까지 올랐을 떄의 최대 점수입니다. 연속된 세 칸 제한에서 첫번째 계단이 포함되지 않기 때문에 무조건 첫번째 계단을 오르고 1칸 올라서 가는 것이 이득입니다. 

하지만 세번째 계단부터는 연속된 세 칸 계단을 오를 수 없다는 제약이 걸리면서 
i번째 계단을 "2칸으로 오르는 경우"와  "1칸으로 오르는 경우"를 비교해야 합니다.

2칸으로 오르는 경우는 계단 하나를 스킵하기 때문에 연속 조건에서 자유롭습니다.
하지만 1칸으로 오르는 경우는 반드시 바로 직전에 2칸으로 올라왔을 떄에만 다음 계단을 1칸으로 오를 수 있습니다.

즉, i번째 계단을 i-1에서 1칸으로 올라가기 위해서는 이전에 i-3에서 2칸으로 i-1을 가야만 합니다.

우선, i-3까지 올라왔을 때의 최대 점수를 구해야 합니다.
우리가 관심있는 건 i번째 계단이므로, i-3번째을 뭘 어떻게 올라왔던지 dp의 성질을 이용하여 항상 최댓값을 가져오기 때문에 dp[i-3]을 사용하면 됩니다. 

그럼 여기에다가 반드시 2칸으로 i-1을 이동한 후, 1칸으로 i로 이동하기 때문에 추가로 "i-1"에서의 점수를 더하면 됩니다.
i-1을 무조건 지나야 하기 때문이죠.

여기까지 정리하면

i을 오르기 위해 이전까지 얻은 점수의 최댓값
1. 2칸으로 올라온 경우 : dp[i-2]
2. 1칸으로 올라온 경우 : dp[i-3] + i-1위치의 점수(stairs[i-1])

여기에다가 i위치의 점수값을 더하면 dp[i]가 완성됩니다.

 

dp[i] = 이전까지 얻은 점수의 최댓값 + stairs[i]