가짜 동전 찾기

 

가짜 동전 문제 설명

 

가짜 동전 찾기 문제는 n개의 동전 중에서 1개의 가짜 동전을 찾는 문제입니다.

가짜 동전은 진짜 동전과 무게가 더 가볍기 때문에 저울을 이용해 찾으려합니다.

먼저 n개의 동전을 반으로 나누어 양쪽 동전의 무게를 잽니다.

그러면 가짜 동전이 포함된 쪽이 더 가벼운 것을 찾아낼 수 있습니다.

이 과정을 반복하면 마지막에는 저울의 양 쪽에 각각 1개씩 남게될 테고 끝내 가짜 동전을 찾을 수 있습니다.

이러한 방법으로 이 문제를 해결하면 시간복잡도는 log2n이 걸립니다.

그렇다면 처음 n개의 동전이 둘로 나눌 수 없는 짝수개일 경우에는 어떻게 해야 할까요?

아니면 동전들을 나누다 보니 동전의 개수가 홀수개가 되어 완벽히 둘로 나눈 수 없을 때는 어떻게 해야 할까요?

 

가짜 동전  찾기 문제에서 만일 동전의 수가 홀수 개이거나 2로 나누다 보니 한쪽이 홀수개 다른 한쪽이 짝수개가 되는 경우를 처리하는 방안을 제시하라.

 

① 주어진 n개의 동전이 홀수일 때(2로 나누기 전)는 1개의 동전을 제외하고 2로 나누어 무게를 잰다. 운이 좋을 경우 가짜 동전을 1번 만에 찾을 수 있고 그렇지 않다고 하더라도 2로 나누어 무게를 잴 수 있다.

 

② 2로 나누다보니 한쪽이 홀수 개, 다른 한쪽이 짝수 개가 되는 경우에는 ①번과 동일하게 동전 1개를 제외하고 무게를 잰다. 예를 들어, 2로 나누어진 결과 동전의 개수가 15가 되었을 때 7개와 8개로 나눌 수 있는 데 이 때 동전 1개를 제외하고 무게를 잰 후, 양쪽의 무게가 같지 않다는 결과가 나왔을 때, 7개의 동전과 아까 제외했던 동전 1개가 남으므로 총 8개의 동전이 된다. 이를 또 2로 나누어 무게를 잴 수 있다.

 

문제 출처 : 1장 연습문제 15번 | 알기 쉬운 알고리즘 | 양성봉 | 생능출판사