n = int(input())
board = [int(input()) for _ in range(n)]
dp = [0]*(n+1)
dp[0] = board[0]
if n > 1:
dp[1] = board[0]+board[1]
if n >2:
dp[2] = max(
dp[1],
board[0]+board[2],
board[1]+board[2]
)
for i in range(3,n):
dp[i] = max(
dp[i-1],
dp[i-2] + board[i],
dp[i-3] + board[i-1] + board[i]
)
print(dp[n-1])
n = int(input())
board = [int(input()) for _ in range(n)]
dp = [0]*(n)
dp[0] = board[0]
if n > 1:
dp[1] = board[0] + board[1]
if n > 2:
dp[2] = board[2] + max(board[1],board[0])
for i in range(3,n):
dp[i] = max(
dp[i - 3] + board[i-1] + board[i],
dp[i-2] + board[i]
)
print(dp[n-1])
두 문제 모두 DP로 푸는 문제이다. 인덱스 i로 이전 dp에 접근하여 조건문으로 해결가능하다. 주의해야할점은 포도주문제의 경우 무조건 마셔야되는 범위가 없지만 계단오르기문제의 경우 세 계단을 가면 무조건 한 계단은 올라야 한다. 이러한 차이점 때문에
dp[i]= k를 설정할때
포도주의 경우 i번째까지 포도주가 존재할때 조건에 맞는 최대양이지만
계단오르기 문제의 경우 i번째 계단이 존재할때 i번째 계단을 포함하여 최대양을 구해야 한다.
따라서 dp[i] 에는 항상 board[i]가 더해지는 것을 코드로 확인할 수 있다.