[알고리즘/동적 계획법] 2156 번 : 포도주 시식 - python

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

2156번: 포도주 시식

---

• 문제
• 소요시간: 38분 15초

---

• 설계하기(접근방법) 

1. n과 포도주를 입력받는다

2. 알고리즘 해석

grape = [6, 10, 13 ,9, 8 ,1]

dp[1] = 6

dp[2] = 6 + 10

dp[3] = max(6 + 13, 10 + 13, 6 + 10)

dp[4] = max(6 + 10 + 9, 6 + 13 + 9, 10 + 13)

dp[5] = max(6 + 10 + 9 + 8,6 + 13 + 9, 6 + 13 + 8, 10 + 13 + 8)

 

이 식을 분석해보면 

dp[4] = max(dp[2] + grape[4], dp[1] + grape[3] + grape[4], dp[3]) 이다

즉 3개의 중복을 피하려면

dp[n-3]에서 grape[n-1]+ grape[n]을 더한것

dp[n-2]에서 grape[n]을 더한 것

혹은

dp[n-1]의 값(현재 항을 더하지 않은 값)

中 하나의 값이 dp의 값이 된다.

 

1 2 .... n 개의 포도잔이 있을 때 

dp[n]의 항에서는

다음과 같이 나뉠 것이다

3개의 포도주가 연속할 수 없으므로

 

dp[n-1] + X

dp [n-2] + n[양]

dp [n-3] + n-1[양] + n[양]

 

3개 중에 max가 dp의 값이 될 것이다

 

3. dp(max)를 출력한다

 

 

 

---

• 코드(출력)

import sys

input = sys.stdin.readline

n = int(input())
grape = []
dp = [0 for _ in range(n+2)]

for i in range(n):
    grape.append(int(input()))

grape.append(0)
grape.append(0)

dp[0] = grape[0]
dp[1] = grape[0] + grape[1]
dp[2] = max(grape[0] + grape[1], grape[1] + grape[2], grape[0] + grape[2])

for i in range(3, n):
    dp[i] = max(dp[i-2] + grape[i], dp[i - 3] + grape[i-1] + grape[i], dp[i-1])


print(max(dp))

---

• 얻어갈 부분

1. 점화식을 세울 때 조건 하나를 놓쳐 다른 분의 식을 조금 참고했다, 예시를 더 꼼꼼하게 쓰고 논리에 벗어나지 않았는지 검토한 후 식을 세우자.