7개의 댓글이 있습니다.
-
-
hyunhwan -
찾아보니 비슷한 질문에 대한 답변이 있습니다. 한번 참고해 보시는게 어떨련까요? 링크 첨부합니다.
http://algospot.com/forum/read/1778/#c8438
10년 전 link
-
-
-
hyunhwan -
조금 더 설명하자면, 책에 처음 나온 방법은 다음과 같은 상태 공간으로 답을 구하는 것입니다. 예를 들어 사탕의 개수가 4개일 경우에 (1,2,1,3)와 같은 상태공간을 헤아리게 됩니다. 여기서 숫자는 첫번째 사탕은 1번에게, 두번째 사탕은 2번 어린이에게, 세번째 사탕은 1번 어린이에게, 마지막 사탕은 3번 어린이에게 건네준다는 이야기지요.
하지만 우리가 궁금한 것은 몇번째 어린이에게 어떤 사탕을 주었는가가 궁금한게 아니라, 가능한 최소의 차이가 얼마인가가 궁금합니다. 따라서 다음과 같이 (120, 140, 160) 과 같이 3차원으로 상태공간을 줄일 수 있게 됩니다. 이는 첫번째 어린이에게는 120만큼의 사탕을 주고, 두번째 어린이에게는 140만큼의 사탕을, 마지막 어린이에게는 160만큼의 사탕을 주었다는 것이지요. 이를 다시 (a, b, c)라고 표현하면 각각 a, b, c에 들어갈 수 있는 숫자의 후보는 최소 0, 최대 20*N이 들어갈 수 있습니다. 따라서 (N*20)^3 가량의 상태공간을 탐색할 수 있는 문제로 바뀌게 되고, 3^N >> (N*20)^3이기 때문에 보다 빠른 시간에 답을 구 할 수 있게 된다는 말입니다.
한번 읽어보시고 이해 안되시는 부분은 댓글 달아주시면 감사하겠습니다!
10년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
juhosung
단순한 방법으로 문제 접근을 하는 예제로 든 부분이 있는데요.
(책30 페이지 입니다.)
N(N<=30)개의 사탕을 세 명의 어린이에게 가능한 공평하게 나눠주려고 하는 문제입니다.. (사탕의 무게는 20이하의 정수입니다.)
해결과정에서 3^N(3^30 => 205조) 방법에서 205조개의 경우의 수 중 각 어린이의 사탕 총량이 같은 경우를 하나로 합쳤을 때에 (N*20)^3
이 된다고 했는데.. 이 부분이 이해가 안 갑니다.
(N*20)^3 이란 뜻이...
어린이 각각 N개의 사탕을 취할 수 있고... 무게는 20가지..
어린이가 3명이니깐 세제곱이 된건가요..???
(N*20)^3은 왜 각 어린이 사탕총량이 가튼 경우는 포함이 안 하는 걸까요..? 아무리 생각해도 이해가 안가네요.ㅠㅠ
답변 부탁드릴께요...
10년 전