파이썬으로 풀어보는 백준 2156번: 포도주 시식

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

 

내 풀이:

N = int(input())
wine = []
for _ in range(N):
    wine.append(int(input()))
 
 
if N == 1:
    print(wine[0])
 
elif N == 2:
    print(sum(wine))
 
else:
    drink_110 = wine[0] + wine[1]
    drink_101 = wine[0] + wine[2]
    drink_011 = wine[1] + wine[2]
    drink_100 = wine[0]
    drink_001 = wine[2]
    drink_010 = wine[1]
 
    for _ in range(3, N):
        drink_110, drink_101, drink_011, drink_100, drink_001, drink_010 = drink_011, max(drink_110, drink_010) + wine[_], max(drink_101, drink_001) + wine[_], drink_110, drink_100 + wine[_], max(drink_101, drink_001)

Python3, 436ms

와인을 마시는 방법은 연속한 3번의 잔에 대해서 2*2*2 인 8가지가 가능하다. 그러나 3잔 연속으로 마시는 drink_111은 문제의 조건으로 불가능하며 3잔을 연속으로 마시지 않는 drink_000은 가운데 잔을 마시는 것이 무조건 최대값이기 때문에 의미가 없다. 따라서 6가지의 방식이 가능하므로 이 6가지에 대해서 비교하여 마지막에 6가지 중 최대값을 출력하는 방식으로 코딩하였다.

 

 

experien님 풀이:

import sys
 
j, f, s = 0, 0, 0
input()
for x in map(int, sys.stdin):
    j, f, s = max(j, f, s), j + x, f + x
 
print(max(j, f, s))

Python3, 60ms

f는 바로 전 와인은 마시지 않았지만 이번에는 마시는 경우이며, s는  전전 와인은 마시지 않았지만 전 와인과 이번 와인을 마시는 경우이다. 중요한건 j인데 j는 이번 와인을 마시지 않는 경우인데 이를 바로 전 j, f, s 중 최대값을 끌고 오는 것이다.