[백준 2156] 포도주 시식

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

 

DP문제입니다. 

 

규칙은 2가지가 있는데

1. 한번 마시면 다 마시고 그 자리에 두어야 함.

2. 세잔을 연속으로 마시지 못함.

입니다.   저는 1번 규칙은 크게 신경 안쓰기로 하고. 2번만 보겠습니다.

 

일단 점화식을 구하기 위해서 현재 내가 선택할잔을 N으로 두겠습니다.

N에 대해서 최대로 마실 수 있는 양을 구하는 방법은

1.  바로 앞(N-1)의 포도주를 마시고 그 앞의 앞 잔(N-3)을 먹은 상태에서 현재의 잔(N)을 먹는 방법

2. 앞의 앞(N-2) 포도주를 마시고 그 앞(N-3) 포도주를 마신상태에서 현재의 잔(N)을 먹는 방법

3. 바로 앞(N-1) 까지 최대치로 먹은 후 현재의 잔을 먹지 않는 방법

 

3가지가 있습니다.

그럼   (arr은 포도주저장한 배열입니다) 점화식은

  D[N] = D[N-2] + arr[N]

  D[N] = D[N-3] + arr[N] + arr[N-1]

  D[N] = D[N-1]

세가지중 가장 큰 값이 되겠습니다.           

 

 

점화식을 구하는건 아직 저한텐 어렵네요.

어떤 상태를 구하고 나서 그것을 점화식으로 옮길때

뭔가 기존생각 밖의 생각을 해야하는거 같습니다.