1문제 분석과 모델링

 

동전 n개 중에는 무게가 적게 나가는 가짜 동전이 한 개 섞여 있습니다. 무게를 숫자로 보여 주는 디지털 저울이 있다면 동전 무게를 차례대로 하나씩 재서 가짜 동전을 간단히 판별할 수 있습니다. 하지만 우리가 사용할 저울은 양팔에 물건을 올리면 어느 쪽이 더 무거운지와 가벼운지만 알려 주는 ‘양팔 저울’입니다.

자, 문제를 좀 더 정형화해 보겠습니다. 동전 개수는 n개이므로 왼쪽에서 오른쪽으로 동전을 일렬로 나열한 다음 맨 왼쪽을 0번으로 하여 차례대로 번호를 붙여 봅시다. 가장 오른쪽에 있는 동전은 n-1번이 됩니다.

 

그림 17-1 n개의 동전을 차례대로 나열하기

 

정리하면, 0번부터 n-1번까지 동전이 있고 이 중에 가짜 동전이 한 개 있는데, 우리가 만들 알고리즘은 양팔 저울로 저울질하여 가짜 동전의 위치 번호를 알아내는 것입니다.