[백준] 2156: 포도주 시식 (Python)

2156: 포도주 시식 (Python)

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

2156번: 포도주 시식

문제

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

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

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

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

입력

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

출력

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

풀이

 맨 처음에는 직전에 마신 경우와 전전에 마신 경우를 고려하여 경우의 수로 문제를 해결하려고 했는데 dp 테이블을 만들고 점화식을 만드는 과정에서 너무 복잡하게 꼬여버렸다. 3번 연속 마시는 경우를 제외한 7가지를 다 dp 테이블로 만들어야 할지 아니면 직전과 전전 경우만 고려해 4가지를 dp 테이블로 만들어야 할지 고민되었다. 결국 경우의 수로 푸는 방법을 포기하고 다른 분의 풀이(https://velog.io/@bye9/백준파이썬-2156-포도주-시식)를 보고 이해했다. 

 

 통용되는 풀이는 다음과 같다. dp 테이블을 1차원 리스트로 생성해 dp[n]에 n번째 잔까지 고려했을 때 최대로 마실 수 있는 양을 저장한다. 따라서 dp[1]는 arr[1]을, dp[2]는 arr[1]+arr[2]로 초기화해준다. 이때 dp와 arr의 인덱스를 맞추기 위해 일부러 arr = [0]로 선언한 후 입력된 값을 append하는 식으로 arr을 만들었다. 이후 점화식은 다음의 세 가지 경우를 고려해 세운다.

1) 직전 잔까지 고려하고 이번 잔은 마시지 않는 경우

2) 전전 잔까지 고려하고 이번 잔을 마시는 경우

3) 전전전 잔까지 고려하고 직전 잔과 이번 잔을 마시는 경우

 이때 고려한다는 것은 해당하는 잔을 마셨거나 마시지 않은 경우의 최댓값이다. 마신 경우도 고려하므로 연속해서 세 잔을 마시는 경우를 제외하여 가능한 경우를 생각해야 한다. 

 

 따라서 점화식은 dp[i] = max(dp[i-1], dp[i-2] + arr[i], dp[i-3] + arr[i-1] + arr[i]) 가 된다.

 dp 테이블의 크기를 상수가 아닌 n을 이용해 만드는 경우에는 반드시 인덱스 에러가 발생할 여지가 없는지 확인하도록 하자. 이 문제의 경우에도 처음에 코드를 그대로 제출했다가 인덱스 에러가 제출해서 보니 for문이 아니라 dp[2]를 초기화하는 과정에서 에러가 발생한 것이었다. 

# 2156: 401 - 다이나믹 프로그래밍 1 연습 - 포도주 시식
n = int(input())
arr = [0]
for i in range(n):
    arr.append(int(input()))
dp = [0]*(n+1)
dp[1] = arr[1]
if n > 1:
    dp[2] = arr[1] + arr[2]
    for i in range(3, n+1):
        dp[i] = max(dp[i-1], dp[i-2] + arr[i], dp[i-3] + arr[i-1] + arr[i])
print(dp[n])

 스터디에서 다른 분이 경우의 수를 이용해 푸신 것을 보았다. 점화식 형태가 되려면 직전 잔과 이번 잔을 마셨는지 마시지 않았는지를 분류할 수 있도록 케이스를 나눴어야 했는데 그 부분을 내가 놓치고 있었던 것이었다. https://github.com/sooyeon73/algorithm_study_2022-/blob/main/6주차_기초401_다이나믹프로그래밍/2156_sy.cpp에서 코드를 확인할 수 있다.