[백준] 포도주 시식

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

2156번: 포도주 시식

다이나믹 프로그래밍을 이용하는 문제입니다.

 

우선 문제부터 요약하면, 

포도주가 시식대에 놓여있는데 이중에서 3개를 연속해서 마실수 없을 때, 최대한 많은 포도주를 마시고 싶을 때, 마신 포도주의 양을 return 해야 합니다. 

 

프로그래머스의 도둑질 문제와 유사합니다. 대표적인 dp문제인데 주로 2개짜리에 대한 이러한 문제는 유명하게 알려져 있습니다. 이 문제 또한 경우를 조금만 더 쪼개서 풀면 됩니다.

 

<Soltuion>

다음과 같이 점화식을 구성하여 해결하면 됩니다.

 

실제 구현은 아래와 같습니다.

import sys

n = int(sys.stdin.readline().strip())
array = [0] * (n+1)
input_array = [0]
for i in range(n):
    input_array.append(sys.stdin.readline().strip())
input_array = list(map(int,input_array))
# print(input_array)

for i in range(1,1+n):
    if i == 1:
        array[1] = input_array[1]
    elif i == 2:
        array[2] = input_array[1] + input_array[2]
    else:
        array[i] = max(input_array[i]+input_array[i-1]+array[i-3], input_array[i]+array[i-2], array[i-1])

print(array[i])