8개의 댓글이 있습니다.
-
-
unbing -
i = 1일 때 맞추기 위해서는 이 아이가 B개의 검은 모자를 보거나 W개의 흰 모자를 보아야 합니다.
i = 2일 때 맞추기 위해서는 이 아이가 B - 1 개의 검은 모자를 보거나 W - 1개의 흰 모자를 보아야 합니다. + 이 아이의 모자가 더해졌을 때 검은 모자가 B개가 되거나 흰 모자가 W개가 되면 안됩니다. (이러면 i = 1이 답이 되버리죠.)
...
i = x일 때는 어떤 경우를 세어보아야 할지 고민하시면 될 것 같습니다. :)
답이 맞다고 입증하기 위해서는 induction을 약간 변형해 보면 되죠.코드를 생각해 보자면 i번 아이가 맞추었을 때, 그 앞의 모자 중 b개가 검은색이고, w개가 흰색이라고 먼저 정합니다 (b와 w가 위의 조건을 만족하게끔). (b + w) choose w개의 가짓수가 있죠. 그러면 i부터 감소하면서 이 아이의 모자의 갯수를 정해줍니다 (다른 아이들이 못 맞춘다는 조건을 만족하면서). 언뜻보면 2^i개의 선택을 해 보아야 할 것 같지만 각각의 i에 대하여 (b, w)만 중요하기 때문에 적은 경우의 수만 memorization을 이용해서 확인해 보면 됩니다. :)
12년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
Andromeda
어제 새벽까지 코딩해서 "맞았습니다!"보고 잤어요.
우와, 신난다.
12년 전