2156번 포도주 시식

포도주가 N개 있다고 가정할 때 나올 수 있는 경우의 수를 구해보자

 

맨 마지막 N개를 포함하는 두 가지 경우와 마지막 N을 포함하지 않는 한 가지 경우 총 3가지로 나누어진다.

 

1. N번째와 N-1번째를 고르고 N-3번째까지의 최댓값을 고르는 경우

2.N번째를 고르고 N-2번째까지의 최댓값을 고르는 경우

3. N-1번째까지의 최댓값을 구하는 경우

 

이를 점화식으로 나타내면(와인을 저장한 wine배열, 총 최댓값을 저장한 dp배열)

 

1. wine[N]+wine[N-1]+dp[N-3]

2.wine[N]+dp[N-2]

3.dp[N-1]

 

그리고 셋 중 제일 큰 값을 고르면 된다.