[BOJ] 2156번: 포도주 시식

https://www.acmicpc.net/

문제 풀이

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

2156번: 포도주 시식

3연속으로 시식할 수 없다는 조건이 제일 중요하다. 다이나믹 프로그래밍을 통해 해결할 수 있는데 첫번 째 포도주 잔부터 마지막까지 하나씩 보면서 해당 잔에서 마실수 있는 최대 양을 구하면 된다. 3연속 조건에 의해 매번 3가지 경우 중에 하나로 판별을 해야한다.

 

현재 잔을 i번째 잔이라고 하면

1. i번째 잔을 마시고 i-1번째 잔을 마셨을 때 i-3번째까지 마실 수 있는 최대 양의 합

2. i번째 잔을 마시고 i-2번째 까지 마실 수 있는 최대 양의 합

3. i번째 잔을 안마셨을 때 i-1번째 까지 마실 수 있는 최대 양의 합

 

3가지 경우 중 최대값을 현재 잔까지 마실 수 있는 최대양으로 구하면 된다.

 

 

Python3

import sys
n = int(sys.stdin.readline())
grapeJuice = [int(sys.stdin.readline()) for _ in range(n)]
if len(grapeJuice) < 3:
    grapeJuice = grapeJuice + [0,0]
dp = [0]*(n+2)
dp[0] = grapeJuice[0]
dp[1] = grapeJuice[0] + grapeJuice[1]
dp[2] = max(dp[1], grapeJuice[0]+grapeJuice[2], grapeJuice[1]+grapeJuice[2])
for i in range(3, n):
    dp[i] = max(dp[i-1], grapeJuice[i]+grapeJuice[i-1]+dp[i-3], grapeJuice[i]+dp[i-2])
print(dp[n-1])

dp[i]는 i번째까지 마실 수 있는 포도주의 최대 양의 합으로 생각한다.

다이나믹 프로그래밍을 사용해 구하기 위해서 초반 3개의 값은 정해주는 것이 필요하다.

첫번째 잔까지 최대 양은 첫번째 잔의 포도주 양이다.

두번째 잔까지 최대 양은 첫번째, 두번째 잔의 포도주 양의 합이다.

세번째 잔까지 최대 양은 이제 3가지 경우에 대해 생각이 필요하다.

=> 첫번째 잔과 두번째 잔을 마셨을 때, 세번째잔과 첫번째 잔을 마셨을 때, 세번째 잔과 두번째 잔을 마셨을 때

 

이후에는 문제풀이에서 적었던 조건처럼 식을 작성해 계속하면된다.

결론적으로 n-1번째의 배열 값을 보면 n번째 잔까지의 최대값이 들어있다.

 

여기서 중요한 점!

dp의 초기 3개의 값을 지정해주기 때문에 n이 1 또는 2일때 문제가 발생한다. 따라서 그 경우에 대한 예외처리가 필요하다. 만약 예외처리를 안해주면 백준에서 컴파일에러를 보게될것,,