[2156]포도주 시식

[2156] 코드

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])

[2579]계단오르기

[2579] 코드

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]가 더해지는 것을 코드로 확인할 수 있다.