문제 1017 독이 든 음식
[만든사람 : ]
문제 설명
SJ왕국의 통치자인 세종이는 왕국을 무너트리려는 첩자를 잡아냈다. 이 첩자는 음식창고에 보관된 T개의 음식 중 하나에 독을 주입했다. 세종이는 독이 든 음식을 찾아내기 위해 독 감지 키트를 사용하기로 했다.
주입된 독은 너무나 강력하여 독이 든 음식은 다른 음식과 섞여도 정확히 일주일 후에 독 감지 키트에 반응한다. 세종이는 일주일 후에 있을 축제에 음식을 사용해야 하기 때문에 시간상 기회는 딱 한 번 뿐이다(단, 독 감지 키트 하나에 여러 음식을 조금씩 섞어 시험할 수 있다).
독 감지 키트는 워낙 고가이기 때문에 '독이 든 음식을 찾아낼 수 있는 최소한의 키트 수 N개'만 구입하려고 한다. 또한, 키트는 독이 한 번 묻으면 다시 사용할 수 없기 때문에 N개의 키트 중에서 '최악의 경우에도 독이 묻을 가능성이 있는 키트의 개수 K개'를 최소화하려 한다. 이 때 N과 K의 값은 얼마인가?
주입된 독은 너무나 강력하여 독이 든 음식은 다른 음식과 섞여도 정확히 일주일 후에 독 감지 키트에 반응한다. 세종이는 일주일 후에 있을 축제에 음식을 사용해야 하기 때문에 시간상 기회는 딱 한 번 뿐이다(단, 독 감지 키트 하나에 여러 음식을 조금씩 섞어 시험할 수 있다).
독 감지 키트는 워낙 고가이기 때문에 '독이 든 음식을 찾아낼 수 있는 최소한의 키트 수 N개'만 구입하려고 한다. 또한, 키트는 독이 한 번 묻으면 다시 사용할 수 없기 때문에 N개의 키트 중에서 '최악의 경우에도 독이 묻을 가능성이 있는 키트의 개수 K개'를 최소화하려 한다. 이 때 N과 K의 값은 얼마인가?
입력 설명
첫 줄에 음식의 수 T가 주어진다.
(2 <= T <= 4,000,000,000,000,000,000)
(2 <= T <= 4,000,000,000,000,000,000)
출력 설명
최소로 필요한 키트의 개수 N
최악의 경우 독이 묻을 수 있는 최소 키트의 개수 K
최악의 경우 독이 묻을 수 있는 최소 키트의 개수 K
입력 예시 복사
3
출력 예시 복사
2 1
도움
3개의 음식(A, B, C)이 있을 경우, 최소한 2개(N)의 독 감지 키트가 있어야지만 어느 음식에 독이 들었는지 알아낼 수 있다. 2개의 키트에 각각 음식 A와 음식 B를 시험할 경우, 키트를 가장 적게 소비하는 최선의 경우는 독이 든 음식이 C인 경우이다. 하지만, 최악의 경우는 독이 든 음식이 A이거나 B인 경우로서, 이 경우에 독이 묻는 최소한의 키트 개수(K)는 1개이다.
출처/분류