BOJ 2695 공

문제 링크:

문제 내용

$B$개의 유리공과 $M$층의 빌딩이 있습니다. 빌딩의 어떤 층에서 공을 떨어트렸을 때 공이 깨지는 최소 높이(1층 이상 $M+1$층 이하)를 알기 위해, 실제로 공을 떨어트려 보는 시행을 하려고 합니다.

유리공은 모두 동일하고 시행 뒤에 깨지지 않은 유리공은 시행 이전의 유리공과 동일하다고 할 때, 가능한 최소 시행 횟수를 구하세요.

$i$층에서 시행을 하게 되면 유리공이 깨지거나 깨지지 않을 수 있습니다. $i$층에서 유리공이 깨졌다면, $B-1$개의 유리공을 가지고 1층부터 $i$층 사이에서 시도해보면 됩니다. 깨지지 않았다면, $B$개의 유리공을 가지고 $i+1$층부터 $M$층 사이에서 시도해보면 됩니다. 이제 $i$들 중에서 최악의 경우의 시행 횟수가 최소가 되는 $i$를 선택하면 됩니다. $B=1$이라면 유일한 방법은 1층부터 순서대로 올라가면서 테스트해보는 것으로, 최악의 경우 $M$번이 소요됩니다.

입력

첫 줄에는 테스트 케이스의 개수 $P$가 주어집니다. ($1 \le P \le 1000$)

각 테스트 케이스에 대해, $B$와 $M$이 한 줄에 주어집니다. ($1 \le B \le 50$, $1 \le M \le 1000$)

출력

각 테스트 케이스에 대해 문제의 정답을 한 줄에 출력합니다.

문제 풀이