[baekjoon] 백준 2156번(파이썬): 포도주 시식

문제

2156번: 포도주 시식

알고리즘

- dp를 통해 포도주의 양을 리스트로 표현한다.

- 현재 포도주를 안 먹는 경우와 연속으로 포도주를 먹는 경우와 이전 포도주를 안 먹는 경우를 비교하여 dp 리스트의 포도주의 양을 넣는다.

코드

import sys

n = int(sys.stdin.readline())
m = [0] * 10001
for k in range(1, n + 1):
    m[k] = int(sys.stdin.readline())

dp = [0] * 10001 # 각 잔까지 먹을 수 있는 포도주 양
dp[0] = m[0]
dp[1] = m[1]
dp[2] = m[1] + m[2]

# 반복문을 통해 각 잔의 최대 포도주 양을 구한다.
for i in range(3, n + 1):
    # 현재 포도주를 안먹는 경우, 연속적으로 포도주를 먹는 경우, 이전 포도주를 안먹고 현재 포도주를 먹는경우
    dp[i] = max(dp[i - 1], dp[i - 3] + m[i - 1] + m[i], dp[i - 2] + m[i])

print(dp[n])

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법