[알고리즘 수학]가짜동전 찾기 문제

문제

크기와 모양이 똑같은 n 개의 동전이 있다.

그 중에 1개의 동전이 가짜 동전이라고 한다.

이 가짜 동전의 무게는 진짜동전과 구별 할 수 없는데 단지 무게만 다르다고 한다.

단, 무게가 가벼운지 무거운지는 모른다.

이때 최소의 횟수로 가짜 동전을 구분 할 수 있는 방법을 찾는 알고리즘을 구현하라.

출처) 길벗 - 알고리즘 퍼즐

 

문제풀이

동전의 무게가 가벼운지 무거운지 안다면 다음과 같이 반씩 나누면서 찾을 수 있을 것이다.

n이 100이라면 50:50 으로 가짜 동전이 있는 쪽을 선택후 25:25 -> 12:12 -> 6:6 -> 3: 3->1:1 과 같이 나누면서 찾을 수 있다.

n이 101이라도 동일한 횟수로 나눌 수 있다. 즉 101 -> 50:50 으로 나눌 수 있다. 여기서 1개는 50:50으로 나누어서 무게가 같다면 1개가 가짜일것이므로~

그렇다면 n개 중에서 가짜 동전의 무게가 가벼운지 무거운지만 판단 할 수 있다면 위와 같은 로직으로 찾아 갈 수 있을 것이다.

만약 100개라면 2개의 동전을 빼고  49:49 로 나누어서 측정하고 같다면 빼 놓은 2개 중에 가짜가 있을 것이다. 이때 찾는 것은 쉬운 문제이다. 양팔 저울에 있는 동전이 진짜동전이므로 이 중 하나와 빼놓았던 2개중 하나와 비교하면 된다.

서로 다르다면 그 중 한쪽을 택한다. 가벼운 쪽을 선택 했다면 그 쪽에서 절반 24:25로 나누고 아까 빼둔 2개중 한개를 추가하여 25:25로 만든다. 이때 무게가 동일하다면 무거운것이 가짜라는 것을 판단할 수 있다. 무거운쪽을 반씩 나눠 가면 최소 횟수로 가짜동전을 찾을 수 있다.

서로 다르다면 가벼운 동전이 가짜 인것을 알 수 있으므로 가벼운쪽을 반씩 나눠 가면 최소 횟수로 가짜동전을 찾을 수 있다.

만약 101개라면 1개의 동전을 빼고 50:50으로 나누어 측정하고 마찬가지로 가벼운쪽을 25:25 로 만들어서 똑같다면 무거운것이 가짜이고 그렇지 않다면 가벼운것이 가짜일 것이다. 이렇게 무게를 알면 반씩 나눠 가면서 최소 횟수로 가짜 동전을 찾을 수 있다.

 

정보올림피아드 예선 문제 유형의 사고력 문제에서 자주 출제 되는 유형으로 원리를 알게 되면 n 의 값이 어떤 수가 나오더라도 해결 할 수가 있다.