문제 소개
물통 1000개가 있다고 가정해 봅시다. 그중 정확히 하나에는 독이 들어 있고, 나머지는 모두 깨끗한 물이 담겨 있습니다. 물통들은 겉보기에 완전히 똑같아서 눈으로 구별할 수 없습니다.
흥미로운 조건이 하나 있습니다. 돼지가 독이 든 물을 마시면 15분 안에 반드시 죽는다는 것입니다. 그렇다면 한 시간(60분) 안에 독이 든 물통을 찾아내려면 최소 몇 마리의 돼지가 필요할까요?
일반화된 문제 정의
이 문제를 일반화하면 다음과 같습니다.
- 서로 다른 물통이 n개 있다.
- 돼지가 독을 마시면 m분 안에 죽는다.
- p분 안에 독이 든 물통을 찾아야 한다.
- 독이 든 물통은 정확히 하나다.
이때 필요한 돼지의 최소 마릿수를 구하는 것이 목표입니다. n = 1000, m = 15, p = 60일 때 정답은 5가 됩니다.
접근 방법: 상태의 개수로 생각하기
핵심 아이디어는 한 마리의 돼지가 구별할 수 있는 상태의 개수입니다. 전체 테스트 시간 p분 동안 돼지는 m분 간격으로 여러 차례 물을 마실 수 있습니다. 따라서 한 마리의 돼지는 다음과 같은 결과를 가질 수 있습니다.
- 첫 번째 시도(m분)에서 사망
- 두 번째 시도(2m분)에서 사망
- … (중략) …
- 마지막(p/m)번째 시도에서 사망
- 끝까지 생존
즉, 한 마리의 돼지는 (p / m + 1)가지 상태를 구분할 수 있습니다. 돼지를 k마리 사용하면 각 돼지의 상태 조합으로 총 (p / m + 1)k개의 경우를 구별할 수 있으므로, 다음 조건을 만족하는 최소의 k가 곧 정답입니다.
(p / m + 1)k ≥ n
로그로 표현하면 k = ⌈log(p/m+1)(n)⌉이며, 1000개의 물통과 (60 / 15 + 1) = 5가지 상태라면 54 = 625 < 1000 ≤ 55 = 3125이므로 돼지 5마리면 충분합니다.
알고리즘 단계
- ret := 0으로 초기화한다.
- (minutesToTest / minutesToDie + 1)ret < buckets 인 동안 ret을 1씩 증가시킨다.
- 반복이 끝난 후 ret을 반환한다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
int ret = 0;
while(pow((minutesToTest / minutesToDie + 1), ret) < buckets) ret++;
return ret;
}
};
main(){
Solution ob;
cout << (ob.poorPigs(1000,15,60));
}입력
1000 15 60
출력
5
정리
이 문제는 단순한 시뮬레이션이 아니라 정보 이론 관점에서 접근해야 하는 대표적인 사고 유형 문제입니다. 각 돼지가 제공할 수 있는 정보량(상태의 수)을 기준으로 필요한 돼지 수를 역산하면, 복잡한 실험 과정을 일일이 따져볼 필요 없이 O(log n) 수준의 간단한 연산만으로 답을 구할 수 있습니다.