[알고리즘] 동적 계획법(Dynamic Programming) - 백준 2156번 포도주 시식

import sys
input = sys.stdin.readline

n = int(input().rstrip())
wine = [int(input().rstrip()) for _ in range(n)]    # [6, 10, 13, 9, 8, 1]
dp = [0] * n

for i in range(n):
    if i == 0:
        dp[i] = wine[i]
    elif i == 1:
        dp[i] = wine[i-1] + wine[i]
    else:
        dp[i] = max(dp[i-1], wine[i]+dp[i-2], wine[i]+dp[i-3]+wine[i-1])

print(dp[-1])

비슷한 문제

백준 - 2579번 계단 오르기
https://velog.io/@minidoo/algorithmbaekjoon2579

계단 오르기 문제와 다른 점은 마지막 포도주를 마시지 않아도 된다는 것이다.

풀이과정

1. wine 배열에 포도주를 넣는다.
2. 포도주가 1잔일 때는 1잔을 마시면 최댓값이 된다.
3. 포도주가 2잔일 때는 2잔을 마시면 최댓값이 된다.
4. 포도주가 3잔 이상일 때는 조건을 둔다. (계단 오르기는 3잔까지 임의로 값을 넣어 주었다.)

• 만약 i번째 포도주를 마시고,
  • i-1번째 포도주도 마셨다면, i-3번째까지 마신 값을 더해준다.
  • i-2번째 포도주를 마셨다면, i-2번째까지 마신 값을 더해준다.
• 만약 i번째 포도주를 마시지 않았다면,
  • i-1번째까지 마신 값을 더해준다.

5. 이 중 최댓값을 구한다.