2방법 ①: 하나씩 비교하기

 

동전 n개에 0부터 n-1까지 번호를 매기고 weigh() 함수를 이용해서 각 동전의 무게를 비교할 수 있도록 모델링을 마쳤습니다.

이제 문제를 풀어 볼 차례입니다. 무게가 적게 나가는 가짜 동전이 한 개만 있다고 했으므로 각 동전의 무게를 비교해서 가벼운 동전이 나온다면 그 동전이 바로 가짜 동전입니다. 0번 동전을 저울의 왼쪽에 올려놓고, 오른편에는 1번 동전부터 차례로 바꿔 가면서 저울질해 보면 가짜 동전을 쉽게 찾아낼 수 있습니다.

0번과 1번 동전을 비교하는 첫 번째 저울질에서 왼쪽이 가볍다면 0번 동전이 가짜 동전이고, 오른쪽이 가볍다면 1번 동전이 가짜 동전입니다. 두 동전의 무게가 같다면 둘 다 가짜 동전이 아니므로 오른쪽에 2번 동전을 올리고 이 과정을 반복합니다.

이렇게 저울질을 하면 마지막 n-1번 동전이 가짜 동전일 경우(최악의 경우) 저울질을 n-1번 해야 가짜 동전을 찾아낼 수 있습니다.

이와 같은 방식을 프로그램으로 만들면 다음과 같습니다.