알고리즘 문제 중
9개의 동전 중 무거운 동전 1개를 찾는 알고리즘을 구하는 문제가 있습니다.
이 때 양팔저울은 2회의 사용기회가 있습니다.
제가 생각하기에
4, 4, 1개로 나누어
1) 첫번째 사용은 4개와 4개를 비교하고
1-1) 둘의 무게가 같다면 1개인 것이 무거운 동전
1-2) 둘의 무게가 다르다면 더 무거운 쪽에 무거운 동전이 포함
2) 1-2의 경우 두번째 사용
2, 2개로 나누어 무게를 재고 무거운 쪽에 무거운 동전이 포함
인데, 어떤 동전이 무거운지 이 방법으로는 2회만에 찾을 수가 없습니다.
2회만에 찾을 수 있는 방법이 있을까요?