13개의 댓글이 있습니다.
-
-
hyunhwan -
http://algospot.com/forum/read/1905/
이 글도 한번 참고해보시길 바랍니다~
11년 전 link
-
-
-
hyunhwan -
사탕 두개를 세명한테 분배할 경우에는 3C2 니까, 총 3개가 맞습니다.
앞의 Being님이 말한 설명을 덧붙이자면 20N은 한사람이 최대한 받을 수 있는 사탕무게의 합이고, 20N+1은 한 사람이 받을 수 있는 사탕의 무게의 경우의 수(아무것도 안받았을 경우에는 0이니 이를 포함함)가 됩니다.
이에 대해서 이런 식으로 생각하면 간단할 것입니다. 각 사람이 받는 사탕의 무게를 (a,b,c)라고 표현하면, a,b,c에는 각각 0이상 20N이하의 숫자가 들어갈 수 있습니다. 따라서, (a,b,c)를 이룰 수 있는 경우의 수는 각각의 무개의 가지 수를 3번 곱한 값이 됩니다.
물론 어림잡아 짐작한 식이기 때문에 실제와는 다릅니다. 왜냐면 (20N,20N,20N)은 당연히 될 수가 없겠죠.
그리고 왜 이런식으로 따져보느냐에 대해서 생각을 해볼 수가 있을 겁니다. 이에 대해서는 정확한 값을 구하는 것 보다는 간단한 수식으로 내가 생각한 알고리즘이 대략 어느정도 수행시간이 필요할까 하는 어림짐작을 위해서 사용을 하는 것이라고 보시면 될 것 같습니다. 많은 경우에 수행시간을 정확하게 분석 하는 자체가 힘들기 때문에, 이와 같은 추정을 통해 '대충 이정도 이상으로 프로그램이 돌지 않을꺼니까 어느정도 구현 할만하겠군?' 하는 감을 얻을 수 있지요.
11년 전 link
-
-
-
JongMan -
이 문제 관련 내용을 3쇄에서 정정하기로 했습니다. 3쇄에 적힐 내용을 여기에서 미리 보실 수 있습니다. 혹시 부족한 점이나 이해가 안 가는 점 있으시면 얼른 알려주세요. ^^;
10년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
precisely
사탕의 개수가 N이고 사탕의 무게는 20이하의 정수일 때 3명의 어린이에게 분배하는 방법의 가지수는? 이라는 문제에서
일단 사탕을 나눠 주는 모든 방법의 가지수가 3^N라고 했는데 사탕의 무게를 이미 알고 있는 경우겠지요..
각 어린이가 받은 사탕 무게가 같은 경우를 하나로 합치면 그 경우의 수가 (N*20)^3이라고 하는데 이건 도대체 어떻게 유도된건가요??
사탕의 개수가 2개라고 가정하고 무게는 항상 1이라고 단순화 시키고 계산해봤는데요, 이 경우에도 (2*1)^3=8인데 뭘 도대체 어떻게 계산하면 8가지 경우가 나온다는 건지 전혀 모르겠네요.. 이건 뭐 입문하자마자 막혀버렸어요.. ㅠㅠ
3이 지수로 가다니 무슨 의미인지 모르겠어요..
11년 전