[백준 BOJ_2156] 포도주 시식 Python 풀이

출처: 백준 온라인 저지

문제

풀이

이 문제에서 중요하게 봐야할 조건은 연속으로 놓여있는 세 잔을 모두 마실 수 없다는 것입니다. 이 부분에서 놓칠 수 있는 부분이 하나 있습니다.

연속으로 놓여있는 세 잔을 모두 마실 수는 없지만 최대로 마실려면 두 잔을 마시고 한 잔만 스킵해야 한다고 생각할 수 있으나, 넘어갈 수 있는 잔의 개수에는 제한이 없기 때문에 두 잔을 스킵할 수도, 세 잔을 스킵할 수도 있습니다. 아래의 반례를 보면 이해하기 쉽습니다.

• 100 $ \rightarrow $ 100 $ \rightarrow $ 1 $ \rightarrow $ 1 $ \rightarrow $ 100 $ \rightarrow $ 100

이 경우에는 첫 번째 잔과 두 번째 잔을 마신뒤 다섯 번째 잔과 여섯 번째 잔을 마셔야 최댓값인 400이 나옵니다. 두 잔을 스킵해야 했습니다. 한 잔만 스킵할 시 제일 마지막 잔을 마실 수 없거나, 그 전의 잔을 마실 수가 없습니다. 결국 400이 아닌 301이 나옵니다.

그렇다면 세 잔을 스킵하는 경우도 고려해야하나 생각할 수 있지만, 세 잔은 고려하지 않아도 됩니다.

• 100 $ \rightarrow $ 100 $ \rightarrow $ 1 $ \rightarrow $ 1 $ \rightarrow $ 1 $ \rightarrow $ 100 $ \rightarrow $ 100

세 잔을 스킵하지 않고 가운데에 있는 1을 포함시키면 됩니다. 두 잔일 때는 중간에서 어느 한쪽을 선택하게 되면 연속된 세 잔을 마시게 되어 버리니 두 잔을 스킵해야 했지만 세 잔부터는 연속되지 않게끔 하나씩 스킵이 가능합니다.

결국엔 고려해야 할 점은

1. 스킵하지 않을 경우
2. 한 잔을 스킵할 경우
3. 두 잔을 스킵할 경우 세 가지 입니다.

동적계획법으로 풀어 보겠습니다. cache의 format은 다음과 같습니다.

# cache[N-1][0 or 1 or 2]
cache[N-1][0]: N-1번째 잔을 마시고 N번째 잔도 마실 때의 최대합
cache[N-1][1]: N-1번째 잔을 마시지 않고 N번째 잔을 마실 때의 최대합
cache[N-1][2]: N-2번째 잔과 N-1번째 잔을 마시지 않고 N번째 잔을 마실 때의 최대합

첫 번째 잔(cache[0])은 스킵하지 않을 경우(cache[0][0])에 첫 번째 잔의 값(wine[0])을 저장해주었습니다.

두 번째 잔(cache[1])은

• 스킵하지 않을 경우(cache[1][0])에는 첫 번째 잔의 스킵하지 않을 경우(cache[0][0])의 값과 자기 자신(wine[1])을 더해준 값을,
• 한 잔을 스킵할 경우(cache[1][1])에는 자기 자신(wine[1])의 값만 저장해줍니다.

세 번째 잔(cache[2])은

• 스킵하지 않을 경우(cache[2][0])에는 두 번째 잔의 한 잔을 스킵한 경우(cache[1][1])의 값과 자기 자신(wine[2])을 더해준 값을,
  • 스킵하지 않았기 때문에 연속해서 두 잔을 마셨으므로 그 전의 잔이 한 잔을 스킵한 경우만 가능합니다.
• 한 잔을 스킵할 경우(cache[2][1])에는 첫 번째 잔의 스킵하지 않을 경우(cache[0][0])의 값과 자기 자신(wine[2])을 더해준 값을,
• 두 잔을 스킵할 경우(cache[2][2])에는 자기 자신(wine[1])의 값만 저장해줍니다.

네 번째 계단부터 조건이 조금 달라집니다. for loop을 3(네 번째 잔)부터 N까지 돌려줍니다.

• cache[i][0] = max(cache[i-1][1], cache[i-1][2]) + wine[i]
  • 스킵하지 않을 경우(cache[i][0])에는 N-1번째 잔(cache[i-1])에서 한 잔을 스킵한 경우(cache[i-1][1])와 두 잔을 스킵한 경우(cache[i-1][2]) 둘 중 최대합이 큰 것을 선택해 자기 자신(wine[i])과 더해준 값을 저장해줍니다.
  • 스킵하지 않았기 때문에 연속해서 두 잔을 마셨으므로 그 전의 잔이 적어도 한 잔을 스킵한 경우만 가능합니다.
• cache[i][1] = max(cache[i-2]) + wine[i]
  • 한 잔을 스킵할 경우(cache[i][1])에는 N-2번째 잔(cache[i-2])의 모든 경우 중 최대합이 큰 것을 선택해 자기 자신(wine[i])과 더해준 값을 저장해줍니다.
• cache[i][2] = max(cache[i-3]) + wine[i]
  • 두 잔을 스킵할 경우(cache[i][2])에는 N-3번째 잔(cache[i-3])의 모든 경우 중 최대합이 큰 것을 선택해 자기 자신(wine[i])과 더해준 값을 저장해줍니다.

마지막으로 꼭 마지막 잔에서 끝나야 한다는 조건은 없었으니, 마지막의 직전의 잔을 마시고 끝나는 경우(cache[N-2])와 마지막 잔을 마시고 끝나는 경우(cache[N-1])의 최대합 중 가장 큰 것을 골라 출력해줍니다.

코드

N = int(input())
wine = [ int(input()) for _ in range(N)]
cache = [[0 for _ in range(3)] for _ in range(N)]
cache[0][0] = wine[0]
if N > 1:
    cache[1][0] = cache[0][0] + wine[1]
    cache[1][1] = wine[1]
    if N > 2:
        cache[2][0] = cache[1][1] + wine[2]
        cache[2][1] = cache[0][0] + wine[2]
        cache[2][2] = wine[2]
        for i in range(3, N):
            cache[i][0] = max(cache[i-1][1], cache[i-1][2]) + wine[i]
            cache[i][1] = max(cache[i-2]) + wine[i]
            cache[i][2] = max(cache[i-3]) + wine[i]
print(max(cache[N-1] + cache[N-2]))