‘저울질’에 해당하는 기능을 프로그램으로 구현할 수 있는 함수를 하나 만들겠습니다.

 

 

weigh() 함수는 a부터 b까지 동전을 양팔 저울의 왼쪽에, c부터 d까지 동전을 저울의 오른쪽에 올리고 저울질하는 함수입니다. 이때 비교하는 동전의 개수는 같다고 가정하였습니다(b - a = d - c).

이 함수 안에 변수 fake를 만들고 우리가 찾아야 할 가짜 동전의 위치를 저장합니다. 가짜 동전 찾기 알고리즘은 fake 변수의 값을 직접 알 수는 없고, weigh() 함수를 호출해서 이 값을 찾아야만 합니다.

weigh() 함수의 결괏값은 -1, 0, 1 세 가지 중 하나입니다. a~b 쪽이 가볍다면 a와 b 사이에 가짜 동전이 있다는 뜻이고, 결괏값으로 -1을 돌려줍니다. 마찬가지로 c~d 쪽이 가볍다면 c와 d 사이에 가짜 동전이 있다는 뜻이고, 결괏값으로 1을 돌려줍니다. 양쪽 무게가 같다면 어느 쪽도 가짜 동전이 없다는 뜻이고, 결괏값으로 0을 돌려줍니다. 이때는 저울에 올리지 않은 동전 중에 가짜 동전이 있다는 의미가 됩니다.

지금까지 설명한 weigh() 함수의 동작을 그림으로 표현하면 그림 17-2와 같습니다.

 

그림 17-2 저울질 기능을 하는 weigh( ) 함수의 동작