arkk20000   1년 전

계단 오르기 DP를 플랫한 느낌으로 2차원 배열에서 1차원 배열로 짜서 구현했는데 소스코드 실행했을 땐 정상적으로 배열 잘 완성되더라구요... 제가 놓친 반례가 있을까요?

jun83   1년 전

dp[i]가 무엇을 의미하는지 명확히 하시고 질문주시면 더욱 양질의 답변을 드릴 수 있습니다.

일단 겉보기로는 각 상태에서 선택이 제대로 이뤄지지 않는 것 같습니다.

+) 2번 건너뛰는 것이 최적해일 때를 놓치신 것 같습니다. 3번 이상 건너뛸 경우 사이에 포도주를 마시는게  최적해임이 자명하여 탐색하지 않아도 됩니다.

일부 문제는 testcase.ac에서 반례를 찾을 수 있습니다.

arkk20000   1년 전

연속으로 놓여진 3개를 마실 수 없다고 하면 39, 30, 0, 19로 88 되지 않는걸까요?

dp[2n]은 계단 오르기로 봤을 때 한 칸 뛰었을 때 값을 의미하고 dp[2n+1]은 두 칸 뛰었을 때 깂으로 두칸 뛰기 전, 그러니깐 두칸 전 요소에서 max(한칸 뛰었을 때 값, 두탄 뛰었을 때 값)으로 비교해서 큰 값을 넣는 방식으로 구현했습니다

arkk20000   1년 전

아아 계단처럼 무조건 두칸 뛰는게 아니고 세칸 떨어져있어도 되네요! 참고 사이트에서 답 얻었습니다! 감사합니다!

jun83   1년 전

6
39 30 5 0 5 19
O O X X O O
이렇게 마시면 93으로 최댓값이 나오게 됩니다.

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