[알고리즘 수학] 전자저울로 가짜 동전 찾기

모양이 똑같은 100개의 동전이 있다.

그중 99개는 진짜 동전이고 하나는 가짜 동전이다.

진짜 동전의 무게는 모두 똑같고 가짜 동전의 무게는 가벼운지 무거운지를 알 수 없지만 진짜동전과 무게는 서로 다른 것만 알 수 있다.

최소 횟수는 몇회인지 찾아내고

3보다 큰 N개의 동전이 입력 되었을 때 가짜 동전을 찾아내기 위한 최소 횟수는 몇번인지 알고리즘을 설계해 보시오.

 

문제풀이)

A그룹 50개, B그룹 50개로 나눈다.

A그룹 50개를 재어 보면 정상적인 동전만 있다면 정상적인 동전 한개의 무게는 총무게/50 이 된다.(1회)

그 다음 A그룹의 25개의 무게를 재 보았을 때 25개의 총무게/25 와 같은지 판별하면 50개의 동전이 정상인지 아닌지 판별 할 수 있다. 만약 50개의 동전이 모두 정상이라면 다른 그룹에 가짜 동전이 있는 것이다. 최악의 경우를 생각해야 하므로 다른 그룹을 살펴 본다.(2회)

B그룹의 25개(B-1)를 판별한다. (3회)

같은 방식으로 정상 동전 그룹이라면 B그룹의 12개(B-2-1)를 판별한다. (4회)  

같은 방식으로 정상 동전 그룹이라면 B그룹의 6개(남은 13개중 절반 B-2-2-1)를 판별한다. (5회)

같은 방식으로 정상 동전 그룹이라면 B그룹의 3개(남은 7개중 절반 B-2-2-2-1)를 판별한다. (6회)

같은 방식으로 정상 동전 그룹이라면 B그룹의 2개(남은 4개중 절반 B-2-2-2-2-1)를 판별한다. (7회)

같은 방식으로 정상 동전 그룹이라면 B그룹의 1개(남은 4개중 절반 B-2-2-2-2-1)를 판별한다. (8회)

 

이런식으로 계산이 되기 때문에 ceil(log2(N)) + 1 과 같이 계산이 되는 것을 알 수 있다.

※ceil 은 올림 즉 log2(100) = 6.643856189775 가 되며 ceil( 6.643856189775 ) = 7 이 된다.