문제
문제 : https://www.acmicpc.net/problem/2579
계단 오르기 게임은 계단 아래인 시작점부터 꼭대기인 도착점까지 가는 게임이다. 계단을 밟으면 계단에 쓰여있는 점수를 얻는다.
예로 들어 시작점에서 첫번째, 두번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 30 = 75점이 된다.
계단을 오를 때는 다음의 규칙을 지켜야 한다.
- 한 번에 한 계단 또는 두 계단 씩 오를 수 있다.
- 연속된 세 개의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다.
- 도착 계단은 반드시 밟아야 한다.
각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.
접근
dp 문제다! 이 글에서는 각 계단에서 두 계단 씩 올라온 경우와 한 계단 씩 올라온 경우 각각의 점수를 테이블에 저장했다.
1. 두 계단 씩 올라온 경우
두 개 이전 계단의 점수의 최대값을 참조한다.
2. 한 계단 씩 올라온 경우
한 개 이전 계단의 점수들을 참조한다. 단, 연속 3개의 계단을 오를 수 없으므로 이전 계단의 이전 계단을 밟은 점수는 제외한다.
이렇게 정리하면 테이블에는 다음과 같은 리스트를 저장하게 된다.
# [두 계단 씩 오른 점수, 한 계단 씩 오른 점수]
[max(dp[-2])] + dp[-1][:-1]두 개 계단 이전 값을 참조해야 하므로, 처음 두 개 계단에 대해서는 하드코딩이 필요하다.
처음에는 최대값 연산을 하지 않고 단순 참조하는 방식으로 풀었는데, 이런 경우 메모리 부족으로 정답 처리가 되지 않았다.
풀이
1. 입력 정보 초기화
계단의 개수와 점수를 입력받는다.
N = int(sys.stdin.readline())
stairs = [int(sys.stdin.readline()) for _ in range(N)]
2. 메모이제이션 테이블 선언
dp = []
3. 테이블 업데이트
[두 계단 씩 오른 점수, 한 계단 씩 오른 점수] 형식으로 저장한다.
for i in range(N):
# 계단 한 개
if i == 0:
tmp = [0, 0]
# 계단 두 개
elif i == 1:
tmp = [0, dp[-1][-1]]
# 그 이상
else:
tmp = [max(dp[-2])] + dp[-1][:-1]
dp.append([t + stairs[i] for t in tmp])
4. 결과 출력
테이블의 마지막 원소 중 최대값을 출력한다.
print(max(dp[-1]))
다른 풀이
조금만 더 생각하면, n번째 계단을 밟는 경우의 수는 단 두 가지이다.
따라서 두 가지 경우의 수 중 큰 값이 n번째 계단을 밟았을 때의 점수가 된다. 이를 식으로 표현하면 아래와 같다.
dp[n] = max(dp[n-3] + stairs[n-1], dp[n-2]) + stairs[n]
구현
import sys
N = int(sys.stdin.readline())
stairs = [int(sys.stdin.readline()) for _ in range(N)]
dp = []
for i in range(N):
if i == 0:
tmp = max(0, 0)
elif i == 1:
tmp = max(stairs[i - 1], 0)
elif i == 2:
tmp = max(stairs[i - 1], dp[i - 2])
else:
tmp = max(dp[i - 3] + stairs[i - 1], dp[i - 2])
dp.append(max(tmp) + stairs[i])
print(dp[-1])