조건

동전 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. ㅁㅁ 2015.07.10 11:31 신고

    근데 이거 양팔저울로 찾는거 아닌가요? 이렇게 하는건 당연한건데..

    • k2man 2015.07.10 15:22 신고

      문제에 조건이 있습니다.
      저울을 가장 적게 사용해서 찾는거에요..^^

  2. 하하... 2015.08.17 21:19 신고

    양팔저울이면 2번이면 될텐데 그냥저울이군요...

    • k2man 2015.08.19 16:59 신고

      오... 양팔저울이면 2번에 가능한가요?
      저는 아무리 생각해도 양팔저울도 3번밖에 안나오는데요. 저좀 알려주세요.^^

+ Recent posts