[LeetCode] 458. Poor Pigs

https://leetcode.com/problems/poor-pigs/description/

leetcode - Poor Pigs

문제 유형 : 수학 / 조합

문제 난이도 : Hard

 

문제

There are buckets buckets of liquid, where exactly one of the buckets is poisonous. To figure out which one is poisonous, you feed some number of (poor) pigs the liquid to see whether they will die or not. Unfortunately, you only have minutesToTest minutes to determine which bucket is poisonous.

You can feed the pigs according to these steps:

1. Choose some live pigs to feed.
2. For each pig, choose which buckets to feed it. The pig will consume all the chosen buckets simultaneously and will take no time. Each pig can feed from any number of buckets, and each bucket can be fed from by any number of pigs.
3. Wait for minutesToDie minutes. You may not feed any other pigs during this time.
4. After minutesToDie minutes have passed, any pigs that have been fed the poisonous bucket will die, and all others will survive.
5. Repeat this process until you run out of time.

Given buckets, minutesToDie, and minutesToTest, return the minimum number of pigs needed to figure out which bucket is poisonous within the allotted time.

 

buckets개의 액체 양동이가 있습니다. 여기서 한 개는 독이 들어있는 액체입니다.

이걸 알아내기 위하여, 당신은 불쌍한 돼지들에게 먹여서 확인해보려고 합니다.

불행히도, 당신은 minutesToTest의 시간밖내로 해야 합니다.

 

당신은 이러한 절차로 돼지를 먹일 수 있습니다.

1. 살아있는 돼지를 고릅니다.

2. 각 돼지에 어느 양동이로 먹일지 정합니다. 돼지가 먹는 시간은 0입니다.

3. minutesToDie분만큼 기다립니다. 이 시간동안에는 다른 돼지들에게 먹일 수 없습니다.

4. minutesToDie분이 지나면, 돼지는 죽거나 살아남습니다.

5. 이를 계속해서 반복합니다.

 

buckets, minutesToDie, minutesToTest가 주어집니다. 정해진 시간 내에 독극물을 찾기 위해서 액체를 먹일 최소한의 돼지의 수를 구하시오.

 

 

풀이

우리에게는 attempts =  minutesToTest / minutesToDie만큼의 턴이 존재합니다.

이 시도횟수 내로 독극물을 판단해야 합니다.

 

만약, buckets=4이고, attempts=3이고 가정합니다.

이런 경우, 돼지 한 마리로 해결할 수 있습니다.

 

첫 번째 턴: 돼지에게 1번 버킷을 먹입니다. 살아남았다면 다음 턴으로 계속합니다.

두 번째 턴: 돼지에게 2번 버킷을 먹입니다. 살아남았다면 다음 턴으로 계속합니다.

세 번째 턴: 돼지에게 3번 버킷을 먹입니다. 살아남았다면 독극물은 4번 버킷입니다.

 

attempts번의 횟수가 있다면, 한 마리의 돼지는 attempts+1가지의 케이스를 해결할 수 있습니다.

p 마리의 돼지는 (attempts+1)^p의 케이스를 만들어낼 수 있습니다.

 

(attempts+1)^p >= buckets를 만족하는 p의 최솟값을 구하면 됩니다.

양변에 로그를 취하여 더 간단히 하면

p = log(buckets)/log(attempts+1)가 나옵니다.

 

 

코드

C++

class Solution {
public:
    int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int pigs = 0;
        int attempts = minutesToTest / minutesToDie;
        while(pow(attempts+1, pigs) < buckets) {
            pigs++;
        }

        return pigs;
    }
};