wbsl0427   4년 전

DP의 대표적인 문제중 하나인 포도주 시식을 풀다가 틀렸습니다라는 문구가 떴습니다.

작은 수와 큰 수들은 전부 넣어봤는데 틀린다고 하네요ㅠㅠ 반례를 찾아 주신다면 감사하겠습니다. 

3시간째 사경을 헤매고 있습니다.

코드 설명 : calculate함수는 최대값을 반환하는 함수로 최대값을 계산하는 역할을 합니다.  포도주를 세번 연속으로 먹을 수는 없기 때문에 한번 먹었을 경우, 두번먹었을 경우로 나누어 재귀를 돌렸습니다. 당연히 DP문제기 때문에 입력값을 저장하는 data배열말고 결과의 최댓값을 저장하는 mem이라는 배열을 추가하였습니다. 한번 먹고 바로 넘길 경우에는 x+2로 함수를 다시 호출하여 한칸을 뛰도록 만들었고, 두번먹고 넘길경우는 두번째까지 이미 먹었기 때문에 x+3을하여 두칸을 뛰어 넘도록 만들었습니다.

처음에 mem을 전부 0으로 초기화 하여 만약 mem에 아무런 값도 없을 경우 그에 해당하는 함수를 호출하여 값을 저장하도록 만들었습니다. 

감사합니다.

lsmin   4년 전

두 번 먹고 넘길 경우에 한칸만 넘기는 경우만 있는게 아니라 두칸 뛰어넘는 경우도 있습니당

예시)

6

2 1 0 0 8 9

이 경우에 2, 1, 8, 9 를 먹어서 21이 나와야 하는데 19가 나오네요^^

wbsl0427   4년 전

앗 그렇군요!! 좋은정보 감사합니다^^

outersky   4년 전

@lsmin

예제 정답 20입니다. 2+8 + 1+9

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