백준 2156 - 포도주 시식

문제

알고리즘 분류)

• 다이나믹 프로그래밍

풀이

이번문제는 dp문제로 "2579-계단오르기"문제와 비슷하다는 것을 느꼈다

3개의 포도주를 연달아 마시지 못하는 규칙이있는 문제이다, 계단오르기와 다른점은 마지막 포도주를 마시지 않아도 되므로 한가지 경우의 수가 추가된다
dp의 핵심인 점화식 구성에 있어 첫번째 포도주부터 경우의 수를 계산해보았다
[6, 10, 13, 9, 8, 1]
첫번째)
첫번째 포도주 밖에 없으므로 dp[0]=array[0] 이다

두번째)
두번째 포도주를 모두 먹으면 되므로 dp[1]=array[0]+array[1] 이다

세번째)
3개를 연달아 마시지 못하므로 1,2번째 2,3번째 중 큰 값을 택하면 된다
dp[2] = max(array[0]+array[1] , array[1]+array[2])

네번째)
지금부터는 점화식을 도출해 주어야 한다.
총 경우의 수는 3가지로
경우1)1,2,4번째 포도주를 먹는 경우 : dp[i-2]+array[i]
경우2)1,3,4번째 포도주를 먹는 경우 : dp[i-3]+array[i-1]+array[i]
경우3)2,3번째 포도주를 먹는 경우 : dp[i-1]
이다, 이 세가지 경우중 가장 큰 값을 택해주면 된다

점화식)
max(dp[i-2]+array[i] , dp[i-3]+array[i-1]+array[i] , dp[i-1])

소스코드

python)

import sys
N = int(input())
array=[0,0,0]+[0]*(N-3)
dp=[0,0,0]+[0]*(N-3)
for i in range(N):
    array[i] = int(sys.stdin.readline())
    
dp[0]=array[0]
dp[1]=array[0]+array[1]
dp[2]=max(array[0]+array[2] , array[1]+array[2] , array[0]+array[1])

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

print(max(dp))