[Python] 백준 2156 포도주 시식

 

문제 분석

• 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있다.
  1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고 마신 후에는 원래 위치에 다시 놓아야 한다.
     (한 번 마신 포도주는 채워지지 않는다. → 방문체크)
  2. 연속으로 놓여있는 3잔을 모두 마실 수 없다.
• 최대한 많은 포도주 맛을 보기 위해 어떤 포도주 잔을 선택해야 할지 고민
• 1 ~ n 번호의 n개의 포도주잔이 테이블 위에 순서대로 있음
• 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램

 

코드 설계

• 이전 단계에서 탐색한 최댓값을 토대로 다음 단계까지 탐색한 최댓값을 구할 수 있다.
  
  
• i번째 포도주까지 탐색했을 때 마실 수 있는 최대 양은?
  1. i번째 포도주를 마시는 경우
     
     • 연속으로 3잔을 마실 수 없다는 조건
     • 1-1) 이전 포도주는 마시고, 전전 포도주는 마시지 않은 경우
       i-3번째까지 탐색했을 때 마실수 있는 최대의 양 + i-1번째 포도주의 양 + i번째 포도주의 양
       dp[ i-3 ] + arr[ i-1 ] + arr [ i ]
     • 1-2) 이전 포도주는 마시지 않고, 전전 포도주는 마신 경우
       i-3번째까지 탐색했을 때 마실수 있는 최대의 양 + i-2번째 포도주의 양 + i번째 포도주의 양
       dp[ i-3 ] + arr[ i-2 ] + arr[ i ]
       dp[ i-2 ] + arr[ i ]
  2. i번째 포도주를 마시지 않는 경우
     • 이전 포도주와 전전 포도주를 마심
       dp[ i-1 ] + dp[ i-2 ] + arr[ i ]
       i-1번째까지의 포도주를 탐색했을 때 마실 수 있는 포도주의 최대 양 : dp[ i-1 ]
       
       
     • 왜 마시지 않는 경우도 체크해야 하는가? (https://www.acmicpc.net/board/view/60664)
       • dp[n]은 n번째 와인까지 따졌을 때 마실 수 있는 와인의 최대 양이다. 이는, 
       • 전전(n-2)까지의 최대 양 + 현재 양
       • 전전전(n-3)까지의 최대양 + 전(n-1)번째 양 + 현재양
         
         
       • 두 가지 경우 중 더 큰 수를 dp에 저장하는 방식이다.
       • 최종 저장된 dp 값을 살펴보면 [6 16 23 28 33 32] 
       • 이때 dp[6]에 33이 아닌 32가 저장된 이유는 현재(n) 와인을 마시지 않은 경우를 고려하지 않았기 때문
       • dp[n-1]에 해당하는 값과 비교하지 않았기 때문이다.

 

정답 코드

실패

import sys
input = sys.stdin.readline

n = int(input())
arr = []
for _ in range(n) :
    arr.append(int(input()))

if n < 3 :
    print(sum(arr))
else :
    dp = [0] * (n+1)

    dp[0] = arr[0]
    dp[1] = arr[0] + arr[1]

    for i in range(2, n+1) :
        dp[i] = max(dp[i-2], (dp[i-3] + arr[i-1])) + arr[i]

    print(dp[n])

 

정답 코드

import sys
input = sys.stdin.readline

n = int(input())
wine = []
for _ in range(n) :
    wine.append(int(input()))

dp = [0 for _ in range(n)]
dp[0] = wine[0]
if n > 1 : # 최소 2잔 있음
    dp[1] = wine[0] + wine[1]

if n > 2 : # 최소 3잔 있음
    # 전전 + 현재 : w[0] + w[2]
    # 전 + 현재 : w[1] + w[2]
    # 전전 + 전 : w[0] + w[1]
    dp[2] = max((wine[0] + wine[2]) , (wine[1] + wine[2]), dp[1])

for i in range(3, n) :
    # 1. 현재의 잔을 마시는 경우
    # 1-1. 전전 마시고, 전 안마심 : dp[i-2] + wine[i]
    # 1-2. 전전 안마시고, 전 마심 : dp[i-3] + wine[i-1] + wine[i]

    # 2. 현재 잔을 안마시는 경우 : dp[i-1]

    dp[i] = max((dp[i-2] + wine[i]), (dp[i-3] + wine[i-1] + wine[i]), dp[i-1])

print(dp[n-1])

 

 

2회차 - 25.03.21

import sys
input = sys.stdin.readline

n = int(input())
wine = [int(input()) for _ in range(n)]

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

dp[0] = wine[0]

if n > 1 :
    dp[1] = wine[0] + wine[1] # 당연히 다 마셔야..

if n > 2 : # 최소 3잔이면, 연속되지 않게 경우의 수 체크
    # 3번째 잔에 대해
    # o x o
    # x o o
    # o o x
    dp[2] = max((wine[0] + wine[2]), (wine[1] + wine[2]), dp[1])

    # o o x o
    # o x o o
    # ? o o x
    for i in range(3, n) :
        dp[i] = max((dp[i-2]+wine[i]), (dp[i-3]+wine[i-1]+wine[i]), dp[i-1])

# print(dp)
print(dp[n-1])