마을에 1000개의 우물이 있습니다. 그런데 그중 독이 든 우물이 하나 있습니다.
독은 치명적이기 때문에 아주 작은 양이라도 독이 든 우물의 물을 돼지에게 먹이면 15분내에 돼지는 죽습니다.
한시간 내로 어떤 우물에 독이 들어있는지 알아내야 합니다.
몇마리의 돼지가 필요할까요? 최소값을 구하시오.
[알고리즘 퀴즈] 필요한 돼지는 몇마리?
시에라(67.186)
2017-06-28 22:01
추천 2
댓글 46
다른 게시글
-
글삭좀 하지마 시벌럼들아 ㅡㅡ [5]ㄹㄷ(121.139) | 17.06.28추천 0
-
std sort qsort기반아님?? [10]익명(210.183) | 17.06.28추천 0
-
막 printf같은 함수들은 저급언어로 정의되있음? [11]죠쓰(onessidotti) | 17.06.28추천 0
-
예전에 istrstr 이었나, 대소문자 안가리는 문자열 비교 함수 최적화 [6]codesafer(codesafer) | 17.06.28추천 0
-
프로그래밍 문외한인데 이런 프로그램 만들려면 오래걸릴까? [2]dd(124.53) | 17.06.28추천 0
-
어차피 머신러닝 알고리즘은 공짜다ㅋㅋ(175.125) | 17.06.28추천 0
-
sort 경연에 대해 안내말씀 드립니다.codesafer(codesafer) | 17.06.28추천 0
-
웹뷰어 끝!!똥쟁이(218.237) | 17.06.28추천 0
-
서당.어징어의 운명은 말이쥬익명(188.166) | 17.06.28추천 0
-
이거 멘사퀴즈래는데 답 알아내는데 얼마나 걸렸는지 적어봐 [7]익명(182.229) | 17.06.28추천 0
흠.... 250? ㅋㅋ
250
그보다 훨씬 적습니다.
sqrt(1000)나 sqrt3(1000)
100마리 해놓고 10개 동시에 쳐먹인다음 반응보는법도 있겠네
한 방에 독든 우물을 고르면 된다 1마리
아 sqrt1000이네
아주 작은 양이라도 독을 먹으면 죽는다는 문구에 주의.
32마리
아직 정답 안나옴.
근데 1~999우물이 멀쩡하고 1000번째에 우물이 독이든거면 어떻게해 ?
8마리 ;;
ceil(sqrt(1000))/4
정답은 5마리입니다. 왜 그런지는 알아서 해결하기 바람.
한 돼지한테 여러개 먹여도되겠구나
근데 숫자를 좁힐수록 돼지는 죽는데 죽는수가 5마리라서 그런겨?
33마뤼
죽는 돼지의 수를 구하는게 아닙니다. 죽는 돼지를 최소화 하려면 1마리만 죽이면 되죠.
[정답] 5마리.... 라고 공개했습니다.
왜 두번만에 해결할라 했지 ㄷㄷ
올ㅋ
플러스님 정답에 가깝지만 1%부족
난 독이작동하는 시간으로봤을때 4타임으로 나눌수있고 x의4제곱이 1000을 넘으면서 가장 가까운 x는 6 그래서 매번 검증되지 않은 우물을 6등분해 각 구역마다 돼지 한마리씩을 배치해 모두 조금씩 먹이게함 하지만 5구역만 배치하고 한구역은 배치를 하지않아도 알수있으니 매 타임마다 투입되는 돼지는 5마리 즉 5곱하기4는 20마리
플러스님 답은 맞는데 식이 틀림, 식도 거의 맞음.
그냥 정답 공개하고 끝냅니다. (60/15 + 1)^5 >= 1000
4진수예요 ? ㄷㄷ;;
이해가 안되요
60/15 = 4이지만 5개의 시약을 테스트 할수 있죠. 1~4번째 테스트에서 죽지않으면 5번째 시약에 독이 든게 확실
제가 바보가 아니란게 증명되어서 기쁘네요. 나도 엄청 헷갈렸음.
왜 난 아무리 생각해도 7마리 멍충멍충
돼지가 한마리일때 가장 효율적인 테스트는 첫번째 우물부터 마지막 우물까지 먹이는 겁니다. 하지만 돼지가 두마리가 될때는 x축 aqrt(n), y축 sqrt(n)으로 2차원 배열을 만든다음 모든 컬럼과 로별 우물을 하나로 섞은 시약을 만들고 독이든 x좌표와 y좌표를 알아낸다면 2마리를 죽임으로써 x, y를 알수있죠.
지렸다
내가 생각한건 4번에 걸쳐서 테스트가 가능하며, 돼지는 한번의 테스트마다 죽는다. n마리의 돼지로 n+1개의 구역을 체크할 수 있으므로 (n-2) * (n-1) * n * (n+1) >= 1000 을 만족하는 최소의 n 7이라고 생각하는데 훔..
오 풀이 지린당 해싱하는 느낌이네
식견을 넓히고 갑니당 ㄳㄳ
나도 오줌 지림
돼지를 3마리 일때는 3차원 그래프를 만들어 x, y, z의 좌표를 합니다. 그럼 각 축은 10의 길이 테스트는 최악의 경우 9번만 하면됩니다. 이경우는 9번의 테스트를 한시간 내에 못하니까안되고, 돼지를 4마리 일때때는 4차원, 5마리일때는 5차원으로 차례차례 연산해서 1시간에 테스트 가능한 최솟값을 구하는 문제입니다.
8마리?
아이디어는 1시간이 15분 단위로 4구간인데, 6*6*6*5 = 1080 > 1000 임. 근데, 저 6마리 중에 한마리만 죽고, 5마리는 재활용가능하니까, 6 + 1 + 1 = 8마리 필요.
6*6*6*5는 무슨 말이냐면, 바이너리 서치처럼 우물들을 6구간으로 나눠서 죽어버리는 돼지가 있는 구간만 다시 재귀적으로 서치하는 거임.
근데, 그 많은 우물을 거의 동시에 한 돼지에게 쳐먹인다는 전제가 성립되야함ㅋㅋㅋ
위에 댓글 읽어봤는데, 1시간에 5번 테스트가 가능?
테스트 결과까지 받아야 되니까 4번이 최대 아닌감;; 멍청멍청
1천개 이진탐색하면 10마리면 되는거 아님?
그리고 15분만에 10마리한테만 먹이면 찾아질걸?
옹 저런 풀이법도 있구나