import sys
def solution(n, stairs):
if n < 3:
return sum(stairs)
dp = [0] * n
dp[0] = stairs[0]
dp[1] = stairs[0] + stairs[1]
dp[2] = max(stairs[0] + stairs[2], stairs[1] + stairs[2])
for i in range(3, n):
dp[i] = max(dp[i-3] + stairs[i-1] + stairs[i], dp[i-2] + stairs[i])
return dp[n-1]
n = int(sys.stdin.readline())
stairs = [int(sys.stdin.readline()) for _ in range(n)]
print(solution(n, stairs))
문제 정의
매 계단마다 주어진 점수가 있고 한 계단 혹은 두 계단 씩 오를 때 최대 점수를 구하는 문제이다. 단, 3번 연속 한 계단씩 오르면 안 된다.
시간 복잡도 계산
계단의 최대 개수는 300개이지만 매 순간마다 해당 계단을 한 계단 뛰어 도착할지 혹은 두 계단 뛰어 도착할지 2가지 경우의 수가 존재하기 때문에 최대 탐색 범위는 2^300으로 매우 크다.
문제 풀이
따라서 DP로 문제에 접근했고 먼저 dp 배열을 정의했다.
dp[i] : i 번째 계단까지의 최댓값
그런 다음 DP 점화식을 구해야 하는데 그 과정이 쉽지 않았다.
먼저 첫 번째, 두 번째 계단까지는 dp 초기항으로서 쉽게 구할 수 있다.
i 번째 항을 생각해 보면 i-1 번째 계단을 거쳐서 오는 것과 (한 계단 뛰어오는 것)
i-2 번째 계단을 거쳐서 오는 것으로(두 계단 뛰어오는 것) 나눠서 생각할 수 있다.
여기서 주의할 점은 i-1 번째 계단을 거쳐서 온다는 것은 i-2 번째 계단은 안 거친다는 것이다. (3개 연속으로 밟을 수 없기 때문에) 따라서 i-3까지의 최댓값에 i-1과 i 번째 점수를 더해주면 된다.
반면에 i-2 번째 계단을 거쳐오는 경우는 단순히 i-2까지의 최댓값에 i 번째 점수를 더해주면 된다.
따라서 점화식은 다음과 같다.
dp[i] = max(dp[i-3] + stairs[i-1] + stairs[i], dp[i-2] + stairs[i])
예외 사항
점화식을 보면 i-3번째 항이 존재해야 사용할 수 있기 때문에 dp[3]까지는 초기항들을 이용해 직접 구해야 한다.