본문 바로가기

백준 문제풀이 코드저장소/Silver

Baekjoon 2156. 포도주 시식 / Python

728x90

2156. 포도주 시식

난이도 : 실버 1
소요 시간 : 15분
날짜 : 2025.01.05
언어 : 파이
알고리즘 유형 : dp

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

  1. 포도주를 선택하면 모두 마셔야 하고, 제자리에 놓아야 한다.
  2. 연속으로 3잔을 마실 수 없다.
  3. 마실 수 있는 포도주 양의 최댓값을 구하기

2. 해결 방식

  1. dp 사용 : dp[i][j] = i번 포도주를 j잔째 마시고 있는 경우 포도주양의 최댓값.
    • 0잔, 즉 i번 포도주를 안먹는다면, dp[i-1]의 값들 중 최댓값이 dp값이다.
    • i번 포도주가 연속된 첫번째 잔이라면, dp[i-1][0]의 값과 dp[i-2]값들 중 최댓값에 현재 포도주 양을 더한 값이 dp 값이다.
    • 두번째 잔인 경우, dp[i -1][1]의 값에 현재 포도주 양을 더해주면 된다.

3. 정답 코드

import sys
input = sys.stdin.readline

n = int(input())

dp = [[0, 0, 0] for _ in range(n)]

for i in range(n):
    now = int(input())
    if i == 0:
        dp[i] = [0, now, now]
        continue
    if i == 1:
        dp[i] = [dp[0][1], now, now + dp[0][1]]
        continue
    dp[i][0] = max(dp[i - 1])
    dp[i][1] = now + max(dp[i - 1][0], max(dp[i - 2]))
    dp[i][2] = now + dp[i - 1][1]

print(max(dp[-1]))
반응형