알고리즘 분류: Dynamic Programming
문제
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.
예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.
계단 오르는 데는 다음과 같은 규칙이 있다.
- 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
- 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
- 마지막 도착 계단은 반드시 밟아야 한다.
따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.
각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.
입력
입력의 첫째 줄에 계단의 개수가 주어진다.
둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.
출력
첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.
예제 입력 1 복사
6
10
20
15
25
10
20예제 출력 1 복사
75[출처: 백준(https://www.acmicpc.net/problem/2579)]
풀이
처음에는 DFS 방식으로 접근하려고 했었는데 잘 안풀려서 보니 대부분 DP로 푸셨더군요. 그래서 저도 DP를 정말 싫어하지만 DP도 공부할겸 DP로 풀어봤습니다.
DP를 사용한 풀이법은 이렇습니다.
문제의 조건에 나와있듯이 연속해서 3칸을 밟고 지나갈 수는 없고 한번에 두칸이나 한칸씩 이동이 가능하다는 조건을 전제로 점화식을 세웠습니다. 더불어 마지막칸은 꼭 밟아야하기 때문에 마지막칸에서 고려했을때 두개의 상황이 나올 수 있습니다.
테스트 케이스에서 주어진 것 처럼 6개의 계단이 있다고 가정할 때 가능한 상황은 다음과 같습니다.
<상황1>
| 6 | 5 | 4 | 3 |
|---|---|---|---|
| 밟음 | 밟음 | X | 밟음 |
dp[n] = steps[6] + steps[5] + dp[3]
<상황2>
| 6 | 5 | 4 | 3 |
|---|---|---|---|
| 밟음 | X | 밟음 |
dp[n] = steps[6] + dp[4]
위의 상황들에서 dp 배열은 dp[n], 즉 n번째 계단까지 갔을 때 가능한 최대 점수를 저장하고 있는 배열이며 steps 배열은 각 계단의 점수를 담고 있는 배열입니다. 저는 이 문제를 풀때 각 배열의 맨 처음에 0을 넣어줘서 인덱스가 헷갈리지 않도록 해주었습니다. 문제의 풀이 소스코드는 아래와 같습니다.
#DP 문제
import sys
steps = [0]
n = int(sys.stdin.readline())
for i in range(n):
steps.append(int(sys.stdin.readline()))
if n == 2 or n == 1:
print(sum(steps))
else:
dp = [0]*(n+1)
dp[0] = 0
dp[1] = steps[1]
dp[2] = max(steps[1]+steps[2], steps[2])
dp[3] = max(steps[1] + steps[3], steps[2] + steps[3])
#점화식1
# dp[n-3] + steps[i-1] + steps[i]
#점화식2
#dp[n-2] + steps[i]
for i in range(4,n+1):
dp[i] = max(dp[i-3] + steps[i-1] + steps[i], dp[i-2] + steps[i])
print(dp[n])
제출하고 통과될 줄 알았는데 런타임 에러가 나와서 살짝 당황했습니다. 런타임 에러의 원인은 보통 인덱스 에러인데 이번 경우에도 마찬가지로 계단의 수가 1개나 2개일때의 예외 처리를 해주지 않아서 인덱스 에러가 발생했습니다. 계단이 한개인 경우의 답은 그 계단의 점수가 답이며 두개일때는 무조건 두개를 밟고 지나가는게 최고로 높은 점수를 획득할 수 있기 때문에 계단 배열의 합을 출력해주었습니다.
그럼 이상으로 백준 - 계단 오르기 문제 풀이를 마치겠습니다. 감사합니다.
*피드백은 언제나 환영입니다. 코드에서 이상한 점이 있거나 고쳤으면 좋겠다 하는 부분들이 있으면 피드백 부탁드립니다 ^^