삼팔저울을 이용한 가짜동전 구별하기
100개의 동전 중 K개의 가짜 동전이 있다.(0<K<100) 가짜 동전은 진짜 동전보다 가볍다.
이를 삼팔 저울을 통해 정확히 찾아내려고 한다. (양팔이 아닌 3개의 팔을 가짐)
- 각 동전은 배열의 요소이다(즉, 가짜동전의 인덱스를 찾아야함)
- 삼팔 저울 함수의 입력값은 세 개의 배열이며, 각 배열은 동전을 몇개든 담을 수 있다.
- 삼팔 저울은 가장 큰 무게만 반환한다. 예) 삼팔저울(A,B,C) //A,B,C 는 각각 동전을 담은 배열 만약 A>B=C 이면 A반환 만약 A=B>C 이면 A,B 반환
가장 쉬운 방법은 저울에 동전을 한개씩 올려 판별하는 방법이다. (반환값이 2개 이하이면, 나머지 한 개는 가짜 동전. 세 개의 값이 같다면 이미 구한 가짜/진짜 동전을 하나 넣어 판별)
삼팔 저울 가장 적게 이용하여 가짜 동전을 정확히 찾아내는 방법은?
가장 빠른 방법은 모든 경우의 수, 즉 2^100을 계산하고 측정할 때마다 아닌 경우의 수를 제외하는 것이다. 하지만 이런 방식은 시간도 오래걸리며 메모리도 많이 사용한다.
다른 방법을 고려하자면 K의 따라 측정 방법을 변경하는 것이다. 예를 들어 K가 1이나 99 정도의 숫자라면 Top-down 형식을 적용하는것이 좋겠고, 중간 정도의 숫자라면 Bottom-up 형식을 적용한다. 상황에 따라 알고리즘을 유연하게 적용하는 방식을 사용하는 것이 좋을것이다.