[S1] 백준 2156 - 포도주 시식 (Python3)

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

---

풀이 아이디어

DP 테이블을 사용하여 각 잔을 선택하는 경우와 선택하지 않는 경우 등을 나누어 최대값을 갱신한다.

풀이👀

1. 포도주 잔이 1개일 때는 그대로 마시는 것이 최대값이므로 DP tabel의 0번째 인덱스의 초기값으로 설정한다.
2. 포도주 잔이 2개일 때는 첫 번째 잔과 두 번째 잔을 모두 마실 수 있으므로 두 잔의 양을 더한 값을 최대값으로 설정한다.
3. 포도주 잔이 3개 이상일 때는 연속으로 3잔을 마실 수 없기 때문에 경우를 나누어 최대값을 갱신한다.
   • case1)  i번째 잔을 마시지 않는 경우: d[i-1]
   • case2)  i-1번째 잔을 마시지 않고 i번째 잔을 마시는 경우: d[i-2] + wine[i]
   • case3)  i-1번째 잔과 i번째 잔을 마시는 경우: d[i-3] + wine[i-1] + wine[i]

---

추가 설명

case1

- 와인을 마시지 않고 넘기는 경우가 득이 되는 때가  있다.

입력:

6

1

1

0

0

1

1

answer : 4

 

case2

- 한 단계 건너 뛰고 시식을 하는 경우이다. 아래에 예시들을 보면 이해가 쉬울 거다.

○:시식X    ●:시식O    ＊:현재위치

● ○ ＊

● ● ○ ○ ● ● ○ ＊

● ○ ● ● ○ ● ○ ＊

 

case3

- 바로 앞의 잔을 시식하는 경우이다. 마찬가지로 아래 예시들을 보자.

○:시식X    ●:시식O    ＊:현재위치

○ ● ＊

● ● ○ ● ＊

● ○ ● ● ○ ● ＊

---

코드🐱‍👓

n = int(input())
wine = [int(input()) for _ in range(n)]

# DP 테이블 초기화
d = [0] * n
d[0] = wine[0]

# DP를 이용하여 최대한의 와인 양 계산
for i in range(1, n):
    if i == 1:
        # 와인 잔이 2잔일 땐 2잔을 모두 선택하는게 최대값이다.
        d[1] = d[0] + wine[1]
    elif i == 2:
        # 와인 잔이 3개일 때, 연속된 2잔을 선택하는 것이 가능하므로 경우를 나누어 최대값을 선택한다.
        # 마시지 않기,  맨 앞잔+현재,  바로 앞의 잔+현재
        d[2] = max(d[1], d[0] + wine[2], wine[1] + wine[2])
    else:
        # 와인 잔이 4개 이상일 때, 경우를 나누어 최대값을 구한다.
        # 1. i번째 잔을 마시지 않는 경우: d[i-1]
        # 2. i-1번째 잔을 마시지 않고 i번째 잔을 마시는 경우: d[i-2] + wine[i]
        # 3. i-1번째 잔을 마시고 i번째 잔을 마시는 경우: d[i-3] + wine[i-1] + wine[i]
        d[i] = max(d[i-1], d[i-2] + wine[i], d[i-3] + wine[i-1] + wine[i])

# 최대 와인 양을 출력
print(max(d))