문제 🍷🥂
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.
- 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
- 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.
예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.
풀이
🍷6 /🍷10/🍷13/🍷9/🍷8/🍷1
이 상황에서
i 번째 포도주를 마시는 상황이라고 가정할 때, i-1 번째 포도주는 마셨을 수도 있고, 안 마셨을 수도 있다.
cur (;i번째 포도주를 마시는 경우) = [i-1 번째 포도주를 마시고 마심,i-1번째 포도주를 안 마시고 마심 ] 이렇게
각 번째마다 cur 리스트를 생성하여서 각 경우를 담아준다고 가정하면,
첫 번째의 경우 ; 더 이전의 포도주가 애초에 존재하지 않으므로 더 이전의 포도주는 안 마신 것과 마찬가지이다.
따라서 첫번째 cur = [0,6]
0 = ❌
6 = 🍷6
두번째의 경우 ; 첫 번째 포도주를 마시고 마심 = 6 + 10 = 16, 첫 번째 포도주는 안 마시고 두 번째만 마심 = 10
16 = 🍷6 /🍷10
10 = ❌ / 🍷10
따라서 두번째 cur = [16,10]
세번째의 경우 ; 두 번째 포도주를 마시고 마심 -> 이 때 포도주를 연달아 세 잔 마시면 안된다는 규칙에 적용받는다 !
따라서 첫 번째 포도주는 안 마시고, 두 번째 포도주만 마신 경우만 두 번째 포도주를 마시고 세 번째 포도주도 마심에 해당할 수 있다.
23 = ❌/🍷10/🍷13 ; 두 번째 cur 의 1번 원소에 13을 더해준 것
두 번째 포도주를 안 마시고 마심 -> 첫 번째 포도주를 안 마실 이유는 없다 ! (포도주를 많이 마실 수록 좋으니깐)
따라서
❌ / ❌ / 🍷13 이 아닌 19 = 🍷6 / ❌ /🍷13 ; 첫 번째 cur 중 최대값에 13을 더해준 것
따라서 세번째 cur=[23,19]
네번째의 경우 ; 세번째 포도주를 마시고 마심 -> 마찬가지로 포도주를 연달아 세 잔 마시면 안 된다는 규칙에 적용받는다 !
따라서 두 번째 포도주는 안 마시고, 세 번째 포도주만 마신 경우만 세 번째 포도주를 마시고 네 번째 포도주도 마심에 해당할 수 있다.
28 = 🍷6 / ❌ /🍷13 / 🍷9 ; 세 번째 cur 의 1번 원소에 9를 더해준 것
세 번째 포도주를 안 마시고 마심 -> 두번째 포도주를 안 마실 이유가 없다 ! (포도주를 많이 마실 수록 좋으니깐)
두 번째 포도주를 마시고, 세 번째 포도주를 안 마신 경우는,
❌ / 🍷10 / ❌ / 🍷9 , 🍷6 /🍷10 / ❌ / 🍷9 두 가지이다. ; 두 번째 cur 의 0번 원소, 두 번째 cur 의 1번 원소
첫 번째 포도주도 안 마실 이유는 없으므로, 25 = 🍷6 /🍷10 / ❌ / 🍷9
따라서 네 번째 cur=[28,25]
다섯번째의 경우, 네번째 포도주를 마시고 마심 -> 마찬가지로 포도주를 연달아 세 잔 마시면 안 된다는 규칙에 적용받는다 !
따라서 세 번째 포도주는 안 마시고, 네 번째 포도주만 마신 경우만 네 번째 포도주를 마시고 다섯번째 포도주도 마심에 해당할 수 있다.
이 때 세 번째 포도주는 안 마시고, 네 번째 포도주만 마신 경우 중 제일 최대값은 네 번째 cur 의 1번째 원소로 이미 구해놓았다.
33 = 🍷6 /🍷10 / ❌ / 🍷9/🍷8 ; 네 번째 cur 의 1번 원소에 8을 더해준 것
네 번째 포도주를 안 마시고 마심 ! 이 때는 좀 생각을 해줘야 한다.
❓/ ❓/ ❓/ ❌ / 🍷8 인 경우는
🍷/🍷 / ❌ / ❌ / 🍷8 일 수 도 있고, ❌/🍷/🍷/❌ / 🍷8 일 수도 있고, 🍷 / ❌ /🍷 / ❌ / 🍷8 일 수도 있다.
각각 두 번째 cur 의 0번 원소, 세 번째 cur 의 0번 원소, 세 번째 cur 의 1번 원소 이다.
두 번째 cur의 1번 원소는 ❌ / 🍷/❌ / ❌ / 🍷8 으로 애초에 최대값이 될 가능성은 없으므로 배제시킨다.
모두 동일한 와인 세 잔씩이므로 각 문제마다 이 세 경우 중 어떨 때가 최대값인지가 다를 것이다. 해당 문제에서는
24 = 🍷 6/🍷 10 / ❌ / ❌ / 🍷8
31 = ❌/🍷 10 /🍷 13 /❌ / 🍷8
27 = 🍷 6 / ❌ /🍷 13/ ❌ / 🍷8 으로 세 번째 cur 의 0번 원소 + 8 인 31이 최대값이다.
따라서 다섯번 째 cur = [33,31]
이제 모든 규칙을 파악하였다 !
첫 번째 cur = [0 , 첫 번째 포도주]
두 번째 cur = [첫 번째 cur 의 1번 원소+두번째 포도주 , 두 번째 포도주]
~ 네 번째의 cur = [i-1번째 cur의 1번 원소+i번째 포도주,i-2번째 cur의 두 원소 중 최대값+i번째 포도주]
다섯 번째 cur ~ = [i-1번째 cur의 1번 원소+i번째 포도주,i-2번째 cur의 두 원소,i-3번째 cur 의 0번 원소 => 총 세 원소 중 최대값+i번째 포도주]
여섯 번 cur 도 동일한 방식으로 구해주면
여섯 번째 cur=[5번째 cur 의 1번 원소 + 1, max(네 번째 cur,세번째 cur 의 0번 원소) + 1]
= [32,29] 가 나온다.
따라서 최종 여섯번째 포도주를 마신 경우,
32 = ❌/🍷 10 /🍷 13 /❌ / 🍷8 /🍷1 (;다섯번째 포도주를 마시고 마신 경우)
vs
29 = 🍷6 / ❌ /🍷13 / 🍷9 / ❌ / 🍷1 (;다섯번째 포도주는 안 마시고 마신 경우)
이므로 ❌/🍷 10 /🍷 13 /❌ / 🍷8 /🍷1 = 32 가 최대 마신 양이다.
한편, 최종 여섯 번째 포도주를 안 마신 경우,
다섯 번째 cur 을 봐주면
33 = 🍷6 /🍷10 / ❌ / 🍷9/🍷8 / ❌
31 = ❌/🍷 10 /🍷 13 /❌ / 🍷8 /❌
이므로 🍷6 /🍷10 / ❌ / 🍷9/🍷8 / ❌ = 33 이 최대 마신 양이다.
32 vs 29 vs 33 vs 31 => 답은 33이다.
최종 정리해주면, dp 식을 세울 때
첫 번째 cur = [0 , 첫 번째 포도주]
두 번째 cur = [첫 번째 cur 의 1번 원소+두번째 포도주 , 두 번째 포도주]
~ 네 번째의 cur = [i-1번째 cur의 1번 원소+i번째 포도주,i-2번째 cur의 두 원소 중 최대값+i번째 포도주]
다섯 번째 cur ~ = [i-1번째 cur의 1번 원소+i번째 포도주,i-2번째 cur의 두 원소,i-3번째 cur 의 0번 원소 => 총 세 원소 중 최대값+i번째 포도주]
마지막 답을 구할 때는,
마지막 번째 포도주를 마신 경우 최대 값 = max(마지막 번째 cur)
마지막 번째 포도주를 안 마신 경우 최대 값 = max(마지막-1 번째 cur)
최종 답은 max( max(마지막 번째 cur),max(마지막-1번째 cur))
import sys
import copy
input=sys.stdin.readline
class Wine:
def read(self):
self.n=int(input())
self.info=[int(input()) for _ in range(self.n)]
def solve(self):
self.dp=[]
for i in range(self.n):
cur=[]
if i==0:
cur.append(0)
cur.append(self.info[i])
self.dp.append(cur)
elif i==1:
cur.append(self.dp[-1][1]+self.info[i])
cur.append(self.info[i])
self.dp.append(cur)
elif i>=5-1:
cur.append(self.dp[-1][1]+self.info[i])
op=copy.deepcopy(self.dp[-2])
op.append(self.dp[-3][0])
cur.append(max(op)+self.info[i])
self.dp.append(cur)
else:
cur.append(self.dp[-1][1]+self.info[i])
cur.append(max(self.dp[-2])+self.info[i])
self.dp.append(cur)
if self.n>1:
cand1=max(self.dp[-2])
cand2=max(self.dp[-1])
ans=max(cand1,cand2)
else:
ans=max(self.dp[-1])
print(ans)
wine=Wine()
wine.read()
wine.solve()
사실 더 쉬운 dp 식이 있을 것이다 ! 🤔 약간 단 와인 마시고 싶다 🍷