SW교육/알고리즘

최소한의 시도로 가짜 동전 찾기

k2man 2015. 3. 29. 21:01
반응형

조건

동전 8개가 있습니다.

동전 8개 중에 진짜 동전은 7개가 있고, 진짜 동전의 무게는 각각 10g입니다.

가짜 동전은 1개가 있고, 무게는 8g입니다.




문제 : 저울을 최소한으로 사용해서 가짜 동전을 찾으세요.

1단계 : 첫 번째 저울 사용

Step 1. 동전을 4개씩 2개의 그룹으로 나눈다. 

Step 2. 둘 중 1개 그룹을 저울을 이용하여 무게를 측정한다. 

Step 3. 만약 1번 그룹(1, 2, 3, 4번 동전)의 무게가 38g이라면, 이 중에 1개 동전은 가짜다. 만약 1번 그룹(1, 2, 3, 4번 동전)의 무게가 40g이라면, 이 중에는 가짜 동전이 없고, 2번 그룹(5, 6, 7, 8번 동전)에 가짜 동전이 있다.



2단계 : 두 번째 저울 사용

Step 1. 전 단계에서 가짜 동전이 있는 것으로 판명된 그룹의 동전을 다시 2개 그룹으로 나눈다. 

Step 2. 1개 그룹 동전을 저울을 이용하여 무게를 잰다. 

Step 3. 1번 그룹(1, 2번)의 무게가 18g이라면, 1, 2번 동전 중 하나는 가짜 동전이다. 1번 그룹(1, 2번)의 무게가 20g이라면, 3, 4번 동전 중 하나는 가짜 동전이다.



3단계 : 세 번째 저울 사용

Step 1. 전 단계에서 가짜 동전이 있는 것으로 판명된 그룹의 동전을 저울을 이용하여 무게를 잰다. 

Step 2. 1번 동전의 무게가 8g이라면, 1번 동전이 가짜 동전이다. 1번 동전의 무게가 10g이라면, 2번 동전이 가짜 동전이다.




자료 다운받기

무른모교육연구소 홈페이지 http://www.swedulab.com 에서 더 많은 자료를 보실 수 있습니다. ^^

반응형

'SW교육 > 알고리즘' 카테고리의 다른 글

이진수 카드 놀이  (1) 2015.03.29
최소한의 시도로 가짜 동전 찾기  (4) 2015.03.29
1 2