[실버 I] 2156번. 포도주 시식

 문제 

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

2156번: 포도주 시식

 사용 언어 

Python3

 풀이 과정 

오랜만에 DP 문제 중에 좀 빠르게 풀었던 것 같다. 문제를 파악하자마자 든 생각은 "나 이거 비슷한거 어디서 풀었는데..?"였고 뒤져보니 예전에 푼 계단 오르기가 거의 유사한 문제였다.

 

그리고 나서 이 문제를 푸려는데 연속으로 3잔을 마시지 않는 방법을 어떻게 처리했는지 생각이 안 나서 결국 계단 오르기 문제에서 내가 풀었던 답변을 참고했다.

from sys import stdin
input = stdin.readline

stairs = int(input())
scores = [int(input()) for _ in range(stairs)]

dp = [0] * stairs
if stairs < 3:
    print(sum(scores))
else:
    dp[0] = scores[0]
    dp[1] = scores[0] + scores[1]
    dp[2] = max(scores[0] + scores[2], scores[1] + scores[2])

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

    print(dp[-1])

계단 오르기와 이 문제의 다른 점은 마지막 계단을 필수로 밟아야 했던 점이다. 이 문제는 마지막 와인을 안 마실수도 있기 때문에(제한이 없음) 경우의 수가 한 가지 더 추가돼야 한다고 생각했다.

 

그래서 생각난대로 풀었더니 예제 문제가 맞아 제출했고, 한 번에 맞았습니다!!

근데 예전에 푼 문제와 유사함에도 비슷하고 참고를 했다는 점은 반성... 복습을 꾸준히 해야겠다.

 

 제출 답안 

from sys import stdin
input = stdin.readline

glass = int(input())
wine = [int(input()) for _ in range(glass)]
dp = [0] * glass

if glass < 3:
    print(sum(wine))
else:
    dp[0] = wine[0]
    dp[1] = wine[0] + wine[1]
    dp[2] = max(dp[1], wine[0] + wine[2], wine[1] + wine[2])
    for i in range(3, glass):
        dp[i] = max(dp[i-1], dp[i-2] + wine[i], dp[i-3] + wine[i-1] + wine[i])
    print(dp[-1])

 

 다른 사람 코드 

1. 엄청 신박한 방법

입력값을 리스트에 저장하지 않고, 바로 9개의 알파벳을 가지고 시뮬레이션을 돌리는 느낌이다.

import sys
read = sys.stdin.readline

def main():
    n = int(read())
    a, b, c, d, e, f, g, h, u = 0, 0, 0, 0, 0, 0, 0, 0, 0
    k = 1
    while k <= n:
        m = int(read())
        tmp3 = max(a,b,c)
        tmp2 = max(d,e,f)
        tmp1 = max(h,u)

        a, b, c, d, e, f = d, e, f, g, h, u
        g, h, u = tmp1 + m, tmp2 + m, tmp3 + m
        k += 1

    print(max(d,e,g,h))

main()

➡ 3년 전이긴 하지만 빠르다는 것!