[백준/Python] 2156번 - 포도주 시식

문제

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

 

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다.

 

1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.

 

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

 

 

 

입력

 

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

 

 

출력

 

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

 

 

풀이

 

연속으로 3잔을 마실 수 없으므로 n 번째 포도주를 안마시거나, 처음 마시거나, 마셨을 때 연속으로 두번째로 마셨거나 총 3가지로 나눌 수 있다.

 

이를 리스트로 만들어 저장했다. 만약 n번째 포도주를 마시지 않는다면, 이전 포도주를 마시지 않고 이번 포도주도 안마시거나, 이전에 마신 포도주가 연속으로 한잔일 때 이번에 안마시거나, 이전에 마신 포도주가 연속으로 두잔일 때 안마시는 경우로 나눌 수 있다.

 

이 중 최대값을 뽑아 리스트의 0번 인덱스에 저장한다. (포도주를 마시지 않았다는 뜻) 그리고 리스트의 1번 인덱스에 이전 n-1번째 포도주를 안 마신 경우와 현재 포도주의 효수를 더해 저장한다.

 

2번 인덱스에는 이전 n-1번째 포도주가 연속으로 한잔일 경우와 현재 포도주의 효수를 더해 저장한다. 이를 반복하고 리스트의 최대값을 구한다.

​

[풀이 요약]

1. 현재 포도주에서 선택할 수 있는 경우의 수는 3가지이다. (안마시기, 연속으로 첫잔, 연속으로 둘째 잔)
2. 길이가 3인 리스트를 만들어 0에는 이번 포도주를 안마신 경우, 1에는 연속으로 첫잔일 경우, 2에는 연속으로 둘째 잔일 경우의 최대값을 저장한다.
3. 포도주의 수 n만큼 반복한 다음 최대값을 구한다.

 

Code

 

 

import sys
input = sys.stdin.readline
N=int(input()) #0, 1, 2, 잔수
ans=[0]*3
lst=[0]*3
for _ in range(N):
    lst=ans[::]
    a=int(input())
    ans[0]=max(lst[0],lst[1],lst[2])
    ans[1]=lst[0]+a
    ans[2]=lst[1]+a
print(max(ans))

 

 

 

 

2156번: 포도주 시식