백준 알고리즘 - 포도주 시식 (2156) [Python]

 문제

 

www.acmicpc.net/problem/2156

2156번: 포도주 시식

 

 

 

 

 

 문제 상황

 

- 포도주를 최대로 마실 수 있는 상황을 정해 그 최대값을 출력한다.

 

 

 

 

 

 해결 전략

 

- i번째 와인을 마시는 경우는 2가지가 있다. i-1번째 와인도 마시되 i-2번째는 안마신 상태일 경우, 혹은 i-2번째까지의 최대값을 구하고 i번째 와인까지 마시는 경우이다. 

 

 

 

 

 

 코드

 

from sys import stdin
input = stdin.readline
N = int(input())
wine = [int(input()) for _ in range(N)]
cache = [0 for _ in range(N)]
cache[0] = wine[0]
if N > 1: cache[1] = wine[0] + wine[1]
if N > 2 : cache[2] = max(wine[0]+ wine[2],wine[1]+ wine[2], wine[0]+wine[1]) 
# i번째 와인까지 최대로 마시는 경우는 i번째 와인을 마시되 i-1을 안먹는 경우, i번째도 먹고 i-1을 마시므로 i-2를 
# 안마시는 경우, i번째 와인을 아예 안마시는 경우 셋 중 하나일 수 밖에 없다.
for i in range(3, N):
    cache[i] = max(cache[i-2]+wine[i], cache[i-3]+wine[i-1]+ wine[i], cache[i-1]) 
print(cache[N-1])
 
# 틀린 코드
# 아래처럼 작성하면 100 100 10 10 100 100 의 경우 원래는 400이 되어야 최대인데
# 100 200 110 210 310 310이 된다. 즉 두번을 점프 뛰어야 하는 상황을 고려하지 못했다.
from sys import stdin
input = stdin.readline
N = int(input())
wine = [int(input()) for _ in range(N)]
# cache[i] = i번째 와인을 마시는 경우 최대의 와인 합
# cache[i] = (i-2번째 와인까지 마신 최대의 합 and i-1 안마시기) or (i-3번째 최대 마신것 and wine[i-1]) + wine[i]
cache = [0 for _ in range(N)]
cache[0] = wine[0]
if N > 1: cache[1] = wine[0] + wine[1]
if N > 2 : cache[2] = max(wine[0],wine[1]) + wine[2]
for i in range(3, N):
    cache[i] = max(cache[i-2], cache[i-3]+wine[i-1]) + wine[i]
print(max(cache))

 

 

 

 해설

 

- dp를 이용해 memoization을 한다. cache의 i번째 요소는 wine이 i번째까지 갔을 때 최대로 와인을 마시는 방법이고, 이는 세가지 경우 중 하나일 수 밖에 없다.(코드에 첨언)

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 점화식을 세울 때, knapsack처럼 dp를 공부할 때 i번째 cache는 i번째 요소를 반드시 포함한다는 고정관념이 있다. 점화식을 세우고 반례를 생각해보면 충분히 도출 할 수 있다.