[Python Algorithm] 포도주 시식 BOJ #2156

문제

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

2156번: 포도주 시식

 

내 문제 풀이

import sys

n = int(sys.stdin.readline())
wine = []
for _ in range(n):
    wine.append(int(sys.stdin.readline()))

if n == 1:
    print(wine[0])
elif n == 2:
    print(wine[0]+wine[1])
elif n == 3:
    print(max(wine[0]+wine[2], wine[1]+wine[2], max(wine[0]+wine[1], wine[0]+wine[2], wine[1]+wine[2])))
else:
    sums = [wine[0], wine[0]+wine[1]]
    sums.append(max(wine[0]+wine[2], wine[1]+wine[2], sums[1]))
    for i in range(3, n):
        sums.append(max(wine[i]+sums[i-2], wine[i]+wine[i-1]+sums[i-3], sums[i-1]))
    print(max(sums))

👉 DP 문제로, 포도주를 마시는 세 가지 조건을 정해주는게 포인트 !

 

포도주를 연속해서 두 번까지 마실 수 있으므로,

하나의 잔 마다 취할 수 있는 자세를 세 가지로 정리할 수 있다.
(wine은 입력받은 포도주들의 리스트, sums는 잔 마다 최대 누적 포도주 양의 리스트이다.)

1. 이 잔을 마시는 대신, 이전 잔은 마시지 않는다.
   => wine[i] + sums[i-2]
2. 이 잔을 마시고, 이전 잔도 마시며, 전전 잔은 마시지 않는다.
   => wine[i] + wine[i-1] + sums[i-3]
3. 이 잔을 마시지 않고, 이전 잔을 마신다.
   => sums[i-1]

위와 같이 구할 수 있는 3가지의 경우의 수 중, 가장 큰 수를 sums에 저장해주면 된다.

 

n이 1부터 3까지는 위의 실행을 정상적으로 진행할 수 없기 때문에 따로 연산했고,

n이 4일 때 부터는 위의 세 가지 조건에 의한 실행으로 작성해주었다. 

 

💡 피드백

• 간단히 생각하면 정말 쉬운 문제일 수 있는데, 나는 너무 복잡하게 생각해버려서 많은 시간을 썼다..,
• 보통의 DP 문제들 처럼, 주어진 입력을 순서대로 각자의 조건을 정해주어 풀면 되는 문제였다.
  DP문제를 오랜만에 풀기 시작하니 다 까먹었나보다,., 많이 공부해야겠다.

---

🖍 [ 추가 ] 다시 풀어보기

import sys

n = int(sys.stdin.readline().strip())
if n == 1:
    print(int(sys.stdin.readline().strip()))
else:
    a = [0] # 현재 포도주를 마시고, 이전 포도주는 마시지 않을 때
    b = [0] # 현재 포도주를 마시고, 이전 포도주도 마실 때
    now = int(sys.stdin.readline().strip())
    a.append(now)
    b.append(now)
    for i in range(2, n+1):
        now = int(sys.stdin.readline().strip())
        a.append(max(max(a[:i-1]), max(b[:i-1])) + now)
        b.append(a[i-1] + now)
    print(max(max(a), max(b)))

👉 첫 풀이때는 세 가지 경우의 수를 만들어주었는데, 이번에는 '#2579 계단 오르기'문제와 비슷하게 풀었다.

 

가장 먼저 생각해주어야 할 두 가지 경우의 수

1. 현재 포도주를 마실 때, 이전 포도주를 마시지 않았다고 가정할 경우라면
   그 전 포도주는 마셨을 수도, 안마셨을 수도 있다. (이 부분이 계단 오르기 문제와의 차이점)
2. 현재 포도주를 마실 때, 이전 포도주도 마셨다면
   그 전 포도주는 마셨으면 안된다.

위와 같이 생각하여 a, b 리스트를 만들어주었고

b의 경우 전전 포도주를 마셨으면 안되기 때문에 바로 a 리스트의 전 누적 값을 추가해주었다.

a의 경우에는 언제 마지막으로 포도주를 마셨는지 모르기 때문에, 이전의 누적 값 중 가장 큰 값을 구해서 추가했다.