4개의 댓글이 있습니다.
-
-
JongMan -
아, 제가 헷갈렸네요. 해당 경우 저는 INF를 반환해야 한다고 생각했는데 아니었군요.
동적 계획법을 구현하신 방법에 문제가 있습니다. next와 n을 키로 사용하셨는데, next와 n이 모두 같아도 답이 다른 경우가 있습니다. picked 때문입니다. picked에 들어가 있는 카메라의 위치들이 {0, 1, 100, 200} 인 경우와 {0, 50, 100, 200} 인 경우를 생각해 보세요. 그러면 남은 장소와 카메라의 개수는 같지만, 기저 사례에서 picked를 순회하며 최소 차이를 찾기 때문에 전자는 무조건 1 이하의 값을 리턴하게 됩니다.
이런 이유로 동적 계획법은 대개 주어진 위치 이후만을 다루는 부분 문제의 최적해를 반환하는 형식으로 구현하셔야 합니다.
9년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
sancho
DARPA 문제 풀다 막혀서.. 글을 남깁니다.
책에서는 결정문제 풀이 밖에 없어서
동적계획법으로 풀어보고 있습니다.
m개의 카메라 중계소에 n개의 카메라를 설치하는 방법은
mCr 이므로, 먼저 조합을 생성하는 재귀 호출을 작성했습니다.
사전 순서대로 조합을 생성하도록 만들고,
아래 코드와 같이 메모이제이션을 적용하였습니다.
예제입력 및 제가 만든 TC는 제대로 동작하는데 자꾸 오답으로 나오네요.
실수처리가 잘못되었나 해서 의심가는 부분은 모두 소수점을 붙였고..
다른 하나의 의심점은 메모이제이션하는 부분인데, 제 생각이 틀린건지요.
미리 감사드립니다.
9년 전