문제: https://www.acmicpc.net/problem/2579
풀이
stair 배열에는 계단의 점수를 받는다.
dp 배열에는 i번째 계단까지 왔을 때 최대가 되는 점수의 합을 저장한다.
조건 3에 따라 마지막 계단(=i번째)을 반드시 밟아야하므로, i번째 계단을 밟았다고 가정해보자.
그렇다면 i-1 계단 혹은 i-2 계단을 밟았을 것이다. (조건2에 따라 둘을 한번에 밟을 수는 없다)
그런데 i-1 계단을 밟았다면 i-3 계단도 반드시 밟아야 한다. i-3을 밟지 않으면 조건1에 위반되기 때문이다.
때문에 dp[i]에 올 값은 stair[i] + dp[i-2]와 stair[i] + stair[i-1] + dp[i-3] 중 최댓값이다.
즉, (현재 계단의 점수 + 두 칸 이전 계단까지의 점수 최댓값)과 (현재 계단의 점수 + 바로 전 계단의 점수 + 세 칸 이전 계단까지의 점수 최댓값) 중 더 큰 값이다.
다만 i < 3 일 때는 위의 계산이 성립하지 않으므로 따로 값을 넣어둔다.
0번 계단은 하나 뿐이므로 stair[0]이고, 1번 계단은 stair[0]+stair[1]일 것이다.
2번 계단은 3칸 연속 밟을 수 없으므로 stair[0]과 stair[2]를 더한 값, stair[1]과 stair[2]를 더한 값 중 최댓값이 들어가야 한다.
이렇게 계단의 개수만큼 dp 배열을 다 채웠으면 그 중 가장 마지막 원소가 최종적인 최댓값이 된다.
소스코드
import sys
input = sys.stdin.readline
n = int(input())
stair = [int(input()) for _ in range(n)]
dp = []
dp.append(stair[0])
dp.append(stair[0] + stair[1])
dp.append(max(stair[0] + stair[2], stair[1] + stair[2]))
for i in range(3, n):
dp.append(max(stair[i] + dp[i-2], stair[i] + stair[i-1] + dp[i-3]))
print(dp[-1])