[ 백준 2156번 포도주 시식 ] Python 코드 (DP)

1. 문제

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

2156번: 포도주 시식

---

2. 아이디어

다이나믹 프로그래밍의 핵심은 DP배열이 가지는 의미 & DP배열을 계산하는 방법이다.

2.1. DP배열이 가지는 의미

지금까지 풀어본 문제들을 보면, DP[n]은 대부분 다음 두 가지 중 하나의 의미를 가졌다.

1. n번째를 선택했을 때의 최적값
2. n번째까지 고려했을 때의 최적값 (n번째를 선택하지 않는 경우까지 고려)

이 문제는 두번째 경우에 해당한다.
왜냐하면 최댓값을 만드는데 있어서 마지막 N번째 포도주를 안 마실 수도 있다.
N번째 포도주를 마시면서 나오는 조합보다, N-1과 N-2를 마시고 끝냄으로써 나오는 조합이 더 클 수 있기 때문이다.
(극단적으로 다른 포도주는 모두 1의 값을 가지는데 N-1과 N-2만 INF를 가지는 경우를 생각해보자.)

따라서 이 문제에서 DP배열 의미를 다음과 같이 정의할 수 있다.
DP[n] == n까지 포도주가 주어졌을 때의 최댓값
즉 n열의 포도주를 선택할 수도, 선택하지 않을 수도 있다.
DP[n]에는 n열의 포도주를 마셨는지 안 마셨는지 정보는 없다. 그저 n열 까지의 포도주가 주어졌을 때 최댓값이 저장되어 있을 뿐이다.

2.2. DP배열의 계산 방법

이 문제는 DP 배열의 계산방법이 생각해내는 것이 관건이다.
또한 "연속해서 3잔을 마실 수 없다."라는 조건 때문에 n열의 포도주가 추가되면서
n-1열과 n-2열의 포도주를 마시는 경우의 수까지 모두 영향을 받기 때문이다.
따라서 n열의 추가 유무에 영향을 받지 않는 DP[n-3]의 값을 가지고 DP[n]을 계산할 것이다.
단순히 n-3열의 포도주를 마시는 경우가 영향을 받지 않는게 아니라,

아래에 설명할 DP배열을 계산하는 아이디어는 이 블로그의 글을 참조했다.
여느 DP문제가 그렇듯이, 이 문제도 나중에 생각해보면 아주 간단하다.
그냥 모든 경우의 수를 고려해주면된다.

위의 7가지 경우의 수는 n열의 포도주를 마시냐 안마시냐에 따라서 4가지(1번 ~ 4번)와 3가지(5번 ~ 7번)로 나뉜다.

Case 1. n열 포도주를 안 마시는 경우
DP[n] = DP[n-1]
n열 포도주를 어차피 안 마실 경우, 직관적으로 최댓값은 DP[n-1]과 같다.
어차피 n열의 포도주를 안 마시기 때문에 없는셈 치면 되기 때문이다.
사실 더 정확히 말하면, 1번부터 4번까지의 경우 중 최댓값이 DP[n-1]에 저장되어 있는 것이다.

Case 2. n열 포도주를 마시는 경우
5번, 6번, 7번 케이스를 비교해보면,
5번 케이스는 결코 최댓값이 될 수 없다. 왜냐하면 7번케이스가 5번을 완벽히 포함하기 때문이다.
그럼 이제 6번 7번에 대한 고려만 진행하면 된다.

• Case 2-1. 6번 . . . . . . O X O
• DP[n] != DP[n-3] + wine[n-2] + wine[n]
• 위의 연산은 사용할 수 없다.
  왜냐하면 우리는 n-3번까지 포도주의 선택이 어떻게 이뤄졌는지 DP배열만으로는 알 수 없기 때문이다.
  만일 DP[n-3]에 저장된 최댓값이 n-3과 n-4를 연속으로 마셔서 나온 결과라면,
  위의 연산은 세번 연속 마실 수 없다면 문제조건을 위반한다.
  
  DP[n] = DP[n-2] + wine[n]
  위의 연산은 6번 케이스를 포함한다.
  물론 포함하지 않을 수도 있다. n-2를 안 먹은 경우가 최댓값으로 DP[n-2]에 저장되어있다면 말이다.
  하지만 상관없다. 그럴 경우 어차피 해당 값은 최댓값으로 선택받지 못한다.
  뒤에 고려할 7번 케이스가 무조건적으로 커지기 때문이다.
  어떻게 보면, n-2를 안 먹은 경우가 최댓값으로 저장되어 있다면, 그건 앞서 제외한 5번 케이스에 해당하겠다.
  
  
• Case 2-2. 7번 . . . . . . X O O
  DP[n] != DP[n-1] + wine[n]
  똑같은 이유로 위의 연산은 사용할 수 없다.
  DP[n-1]에 저장된 최댓값이 어떠한 경우의 수를 가리키는지 알 수 없기 때문이다.
  DP[n-1]에 저장된 최댓값이 n-1과 n-2를 연속으로 마셔서 나온 결과라면,
  위의 연산은 세번 연속 마실 수 없다면 문제조건을 위반한다.
  
  DP[n] = DP[n-3] + wine[n-1] + wine[n]
  위와 같이 계산해야 문제조건을 위반할 경우를 모두 제외할 수 있다.
  어찌되었든 DP[n-3]에 저장된 값은 문제조건을 만족하는 최댓값이 저장되어 있고,
  wine[n-2]를 건너뜀으로써 wine[n-1], wine[n]과의 연결성을 끊어버렸다.

이렇게 DP배열 담긴 의미를 잘 해석해서 이용함으로써, 모든 7가지의 경우의 수를 3가지로 표현할 수 있다.

---

3. 코드

포도주의 길이가 2이하로 주어질 때만 적절히 케이스를 나눠서 코드를 짰다.

import sys
input = sys.stdin.readline

N = int(input())
juices = [0] * N
for i in range(N):
    juices[i] = int(input())

# 주어진 포도잔의 길이가 1일 경우
if N == 1:
    print(juices[0])

# 주어진 포도잔의 길이가 2일 경우
elif N == 2:
    print(juices[0] + juices[1])

# 주어진 포도잔의 길이가 3이상일 경우
else:
    DP = [0] * N                # DP배열 선언
    DP[0] = juices[0]           # DP[:3]까지 초깃값 셋팅
    DP[1] = juices[0] + juices[1]
    DP[2] = sum(juices[:3]) - min(juices[:3])
    
    # 메인 아이디어
    for i in range(3, N):
        DP[i] = max(DP[i-1], DP[i-2] + juices[i], DP[i-3] + juices[i-1] + juices[i])

    print(DP[-1])