dp[i]가 무엇을 의미하는지 명확히 하시고 질문주시면 더욱 양질의 답변을 드릴 수 있습니다.
일단 겉보기로는 각 상태에서 선택이 제대로 이뤄지지 않는 것 같습니다.
+) 2번 건너뛰는 것이 최적해일 때를 놓치신 것 같습니다. 3번 이상 건너뛸 경우 사이에 포도주를 마시는게 최적해임이 자명하여 탐색하지 않아도 됩니다.
일부 문제는 testcase.ac에서 반례를 찾을 수 있습니다.
2156번 - 포도주 시식
dp[i]가 무엇을 의미하는지 명확히 하시고 질문주시면 더욱 양질의 답변을 드릴 수 있습니다.
일단 겉보기로는 각 상태에서 선택이 제대로 이뤄지지 않는 것 같습니다.
+) 2번 건너뛰는 것이 최적해일 때를 놓치신 것 같습니다. 3번 이상 건너뛸 경우 사이에 포도주를 마시는게 최적해임이 자명하여 탐색하지 않아도 됩니다.
일부 문제는 testcase.ac에서 반례를 찾을 수 있습니다.
댓글을 작성하려면 로그인해야 합니다.
arkk20000 1년 전
계단 오르기 DP를 플랫한 느낌으로 2차원 배열에서 1차원 배열로 짜서 구현했는데 소스코드 실행했을 땐 정상적으로 배열 잘 완성되더라구요... 제가 놓친 반례가 있을까요?