[백준 2156번] 포도주 시식 파이썬 풀이

포도주 시식 

2 초

128 MB

136592

46651

33732

32.661%

문제

 

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

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

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

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

입력

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

출력

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

예제 입력 1

6
6
10
13
9
8
1

예제 출력 1

33

 

최근에 다이나믹 프로그래밍 문제에 맛들려서 이번 문제도 다이나믹 프로그래밍이다.

여담이지만 내가 풀은 모든 문제를 포스팅하는것은 아니고, 풀면서 정리할 필요가 있다고 느껴지거나 독특하다고 느껴진 문제들만 정리할 목적으로 포스팅하고 있다.

 

해당 문제를 풀기 위해선 문제에서 주어진 2가지 조건에 주목해야 한다.

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

 

마신 후에 원래 위치에 다시 놓아야 한다는것은 현실세계의 이야기이니 복잡하게 생각할것 없이, 그냥 큰 수를 만들기 위해 카드를 선택한다고 생각하면 된다. 단 3장의 카드를 연속해서 고를수 없음이 2번째 조건에 해당된다.

 

무슨 이야기인지 이해를 돕기위해 다음과 같은 예시를 들어보겠다.

다음과 같이 배열에 숫자들이 담겨있다고 가정해보자.

 

977 / 200 / 517/ 851/ 23

 

2가지 규칙에 따라 숫자를 골라 최대합을 만든다고 가정할때,

0번째는 당연히 977을 골라 dp[0] = 977이 될 것이고,

1번째도 마찬가지로 200을 추가로 골라 dp[1] = 977 + 200 = 1177이 될 것이다.

 

하지만 2번째 경우부터는 조금 달라진다. 만약 517을 고르게 된다면, 977, 517을 고르거나 200, 517을 고르거나 둘 중의 한 경우를 선택해야 하기 때문이다.(규칙 2 : 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.)

그럼 여기서 max(977+517, 977+200)을 하여 두 수중 최대합을 고르면 되는것이 아닌가? 하고 생각할 수 있는데(처음에 이렇게 생각해서 오답판정을 받았었다.) 사실, 카드를 고르지 않는 경우가 최대합이 될 수도 있으므로, 카드를 고르지 않는경우까지 고려하여 3가지 경우 중 최대합을 dp테이블에 기록해야한다!

 

이것이 무슨말이냐 하니, 만약 수가 10 / 20 / 5 이렇게 있다고 가정해보자.

그렇다면 5를 고르지 않고 10,20 두 개의 카드를 골라 30이 정답이 되는 것이나, 만약 수가 10,20,21 과 같아면 20,21을 골라야 정답이 되고, 수가 21,20,23 이라면 21,23을 골라야 정답이 되기 때문이다.

 

이러한 원리를 이해하였다면 이제 점화식을 세워볼 수 있다.

아래 식에서 data는 입력받은 카드의 배열이고, dp는 해당 인덱스의 경우에서 최대합을 의미한다.

 

dp[i] = max(dp[i-1], data[i]+data[i-1]+dp[i-3], data[i]+dp[i-2])

 

식을 해석해보면 배열에서 i번째 최대 합은 카드를 고르지 않은경우(dp[i-1])와 현재 인덱스 이전의 카드를 고른 경우(data[i]+data[i-1]+dp[i-3]) 와 현재 인덱스의 이전이전 카드를 고른 경우(data[i]+dp[i-2]) 중 최대 값을 i번째 최대 합으로 기록하겠다는 의미이다.

점화식을 세울 수 있는 이유는, 이전의 선택들도 모두 같은 결론을 통해 기록된 결과일 것이기 때문이다.

 

위의 이론을 이해하였다면 아래 코드를 살펴보길 바란다.

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

n = int(input())

# 최대로 마실 수 있는 포도주의 누적합을 저장할 배열
dp = [0]*n

# 포도주를 저장할 배열
data = []

# 포도주의 양 입력받기
for i in range(n):
    data.append(int(input()))

# 포도주는 마실수도 있고, 안마실수도 있으므로 => 해당 잔을 마시는것이 이득인지, 손해인지를 따져서 선택해야한다.
for i in range(n):
    # 1번째와 2번째잔만 존재하는 경우에는 포도주를 마시는것이 이득이므로 마신다.
    if i == 0:
        dp[0] = data[0]
    elif i == 1:
        dp[1] = data[0] + data[1]
    # 3번째 잔부터는 포도주를 마시는경우와 마시지않는경우를 고려한다.
    elif i == 2:
        dp[2] = max(data[0]+data[1], data[0]+data[2], data[1]+data[2])
    # 4번째 잔부터는 해당잔을 마시느냐 안마시느냐에 따라, 이전잔을 못마실수도 있으므로 점화식을 달리한다.
    else:
        # 포도주를 안마시는 경우는 해당 잔 이전까지의 누적합이 최대가 된다. dp[i] => dp[i-1]
        dp[i] = max(dp[i-1], data[i]+data[i-1]+dp[i-3], data[i]+dp[i-2])


# 반복문 종료이후 dp테이블의 최대값을 출력한다.
print(max(dp))

 

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

2156번: 포도주 시식