백준 2156 파이썬 - 포도주 시식 - 동적 계획법

백준 2156 파이썬

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

2156번: 포도주 시식

해당 문제는 주어진 조건에 의해 가장 많은 양의 포도주를 시식하는 방법을 구하는 문제입니다.

• 포도주의 잔을 선택하면 모두 마셔야한다.
• 연속으로 놓여 있는 3잔을 모두 마실 수 없다.

[CS/알고리즘] - 백준 2579 파이썬 - 계단 오르기 - 동적 계획법 문제와 유사한 문제인데 차이가 있다면 가장 마지막 잔을 꼭 마시지 않아도 된다는 것입니다. 즉, 최대값을 구할 때 조건이 하나 더 붙을 거라는 예정입니다.

 

연속으로 3잔을 마시지 못하기 때문에 최대로 연속 2개의 와인을 마실 수 있습니다. 그리고 마지막 와인을 꼭 마실 필요는 없습니다. 이런 한 조건으로 아래와 같은 규칙이 생깁니다.

• 현재 위치의 와인을 마시고 바로 전 와인을 마셨다는 것은 -3 위치의 최대값에서 하나 건너 뛴 경우다.
• 현재 위치의 와인을 마시고 이전 와인이 건너 뛴 와인이라면 -2 위치의 최대값을 더한 경우다.
• 현재 위치의 와인을 마시지 않았다면 -1 위치의 최대값이 현재 위치의 최대값이다.

case 1과 case2의 조건은 마지막 잔을 무조건 마셔야하기 때문에 계단 오르기 문제와 똑같습니다. 그러나 이번 문제에서 다른 조건은 마지막 와인을 꼭 마시지 않아도 되기 때문에 건너 뛸 수 있습니다.

 

 

Python 풀이

import sys
read = sys.stdin.readline

N = int(read())
wines = [0] + [int(read()) for _ in range(N)] + [0]
dp = [0] * (N+2)
dp[1] = wines[1]
dp[2] = dp[1] + wines[2]

for i in range(3, N+1):
    dp[i] = max(dp[i-3]+wines[i-1]+wines[i], dp[i-2]+wines[i], dp[i-1])
print(dp[N])

• 1과 2의 위치까지는 최대값이 연속으로 마신 경우이므로 초기값을 지정해준다.
• 초기값 설정에 때라 dp의 리스트 길이를 초기값 만큼 더하고 wines 양쪽에도 리스트 길이를 추가한다.
  • N이 1 인 경우 wines[2] 때문에  Index out of bounds 오류가 발생한다.
• 조건에 맞게 최대값을 구해서 출력한다.