furyhunter   7년 전

동적계획법을 적용해 이전 단계의 최댓값을 저장하여 문제를 해결하려고 하는데

포도주를 연속 3번 마실 수 없기 때문에

1) 이전 단계의 값이 포도주를 연속 한잔 마신 경우와

2)연속 두잔 마신 경우로 나누어 봤습니다.


1. 이전 단계에서 포도주를 처음 마신 경우,

전전 번의 포도주는 마시지 않은것이 되므로 전전전 단계의 최댓값 + 직전의 포도주 + 현재의 포도주

2. 이전 단계의 포도주가 2번째 포도주일 경우,

현재의 포도주는 마실 수 없고 건너 뛰어야 하기 때문에 직전 단계의 최댓값을 저장합니다.


이 값들을 각각 dp[][0]과 dp[][1]에 저장해봤습니다.

주어진 예제 6 / 6 10 13 9 8 1 의 경우,


                0    6   10   13    9    8    1

dp[][0]    0    6   16   23   28  33  32

dp[][1]    0    6    6    16   23  28   33

 하는 식으로 답이 나와서 최종적으로는 정답인 33이 출력됩니다.

그런데.. 몇가지 케이스를 더 테스트해봤는데 정답이 나와서 제출해보니 오답이 납니다.

혹시 제 생각에 논리적으로 뭔가 오류가 있나요?

아니면 이 방법의 예외가 되는 케이스가 있을까요?

jung2381187   7년 전

3

10 1 10


11 출력되네요

allkanet72   7년 전

복잡하게 전단계를 기준으로 삼지 말고 현재를 기준으로 풀어보세요.현재 포도주 1번 마셨을때 2번 마셨을때 안마셨을때. 이렇게 3가지 경우로 나누면 됩니다. 

댓글을 작성하려면 로그인해야 합니다.