BOJ 2156: 포도주 시식

오늘도 계속되는 dynamic programming!

BOJ 2156: 포도주 시식

n=int(input())
data=[]
for i in range(n):
  data.append(int(input()))
dp=[0]*n
dp[0]=data[0]
if n>1:
  dp[1]=data[0]+data[1]
if n>2:
  dp[2]=max(data[0]+data[2], data[1]+data[2], data[0]+data[1])
for i in range(3,n):
  dp[i]=max(dp[i-2]+data[i],dp[i-3]+data[i-1]+data[i],dp[i-1])


print(dp[n-1])

이 문제에서는, 3번 연속으로 와인을 마시면 안된다.

그렇기에, 3개 이상의 와인이 시식 가능할 때, 

 

i-3   i-2   i-1   i

i-3   i-2   i-1   i

i-3   i-2   i-1   i

 

(볼드체는 dp에서, 볼드체 및 밑줄은 data. 즉 해당 index의 와인을 구매하는 것이다.)

 

이 문제가 특히 더 어려웠던 건, 2칸 이상 띄어서 와인을 먹을 수 있기 때문이다.

예를 들면, 100 100 1 1 1000 같은 경우에는,

100 100 1000을 먹는게 제일 좋다.

이런 경우를 위해서 '2개 먹고 하나 쉬고' 하는 것은 best한 전략은 아닌 것이다.

 

오늘도 화이팅.!