[백준][다이나믹] 2156 포도주 시식

포도주 시식은 포도주를 

첫번째로 마시는 경우, 

두번째로 마시는 경우, 

마시지 않는 경우로 나누어서 생각하면 해결할 수 있다. 

6개의 와인잔이 1000, 900, 2, 1, 800, 700 의 순서로 놓여져 있는 경우 다음과 같이 생각할 수 있다. 

순서	1	2	3	4	5	6
첫 번째로 마시는 경우	1000	900	1002	1901	2700	2601
두 번째로 마시는 경우	0	1900	902	1003	2701	3400
마시지 않는 경우	0	1000	1900	1900	1901	2701

3번의 경우에 

첫 번째로 마시는 경우는 이전에 마시지 않는 경우에서 자신을 더하는 것이다. -> 1000 + 2 = 1002

두 번째로 마시는 경우는 이전에 첫번째로 마시는 경우에 자신을 더하는 것이다. -> 900 + 2 = 902

마시지 않는 경우는 이전의 모든경우 중 최대값이다. -> 900, 1900, 1000 중에서 최대값 1900 이 된다. 

이를 반복하면 문제를 해결 할 수 있다. 

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