23800번 - 많이 튼튼한 금고 테스트

지금 우리에게 \( N \)층 빌딩과 새로 개발한 동일한 모델의 \( K \)개의 금고가 있다. 우리들은 이 신형 금고의 견고함을 측정하려고 한다.

이 금고가 충격을 견딜 수 없어 깨지기 시작하는 높이의 층을 \( F \)층이라고 하자. 다시 말하면, \( F \)층을 포함하여 그 위의 층에서 금고를 떨어뜨리면 무조건 부서지며, \( F \)층의 아래층에서 금고를  금고는 절대 부서지지 않는다. \( N \)층에서도 부서지지 않을 수도 있으며, \( 1 \)층에서도 부서질 수도 있다. 각각의 경우에 대해서 \( F \) 값은 각각 \( N+1, 1 \)로 정해진다. 우리가 \( F \)의 값을 정확히 구해내면 견고함을 성공적으로 측정한 것으로 생각한다.

이 값을 정확히 구하기 위하여 우리는 특정한 층에 올라가 직접 금고를 하나 떨어뜨려 보는 테스트를 할 수 있다. 모든 금고의 견고함은 동일하며, 금고가 부서졌으면 그 금고를 다음 테스트부턴 다시 사용할 수 없고, 부서지지 않았다면 다시 사용할 수 있다.

우리는 이 \( N \)층 짜리 건물에서 \( K \)개의 금고를 가지고 언제나 성공적으로 측정하기 위한 최소 테스트 횟수를 구하려고 한다.

예를 들어, \( N=10, K=1 \)인 경우를 생각해보자. 만약 \( 4 \)층에서 테스트를 시도하고 금고가 부서지지 않았다면 \( F \)는 \( 5 \) 이상이란 결론이 나온다. 그러나 두 번째 테스트를 \( 6 \)층에서 시도했을 때 금고가 부서졌다면 \( F \)의 값이 \( 5 \)일지 \( 6 \)일지 모르는 상태에서 멀쩡한 금고가 없기 때문에 이 경우에는 \( F \)값을 알아내는 데 실패한 경우가 된다. 따라서 최악의 상황에도 \( F \)층을 정확히 알아내려면 \( 1 \)층부터 \( 10 \)층까지 차례대로 한 번씩 떨어트려 봐야 하므로 이 경우에는 \( 10 \)회가 정답이 된다.

이번엔 금고가 하나 추가되어 \( N=10, K=2 \)인 경우를 생각해보자. 만약 처음에 \( 4 \)층에서 떨어트린다고 하면, 금고가 부서졌을 땐 \( 1, 2, 3 \)층을 차례로 테스트해 봐야 하니 이때는 최대 \( 4 \)번 테스트하게 된다. 그러나 금고가 부서지지 않았다면 다음번엔 \( 7 \)층에서 테스트한다. 이때 부서졌다면 \( 5, 6 \)층을 차례대로 시도하고, 부서지지 않았다면 세 번째 시도에 \( 9 \)층을, 이때 부서졌다면 네 번째에 \( 8 \)층을, 부서지지 않았다면 \( 10 \)층을 시도하면 된다. 이 방법으로 테스트를 한다면 최악의 경우 \( 4 \)번만에 정확한 \( F \)값을 알 수 있고 이보다 더 적은 횟수로 가능한 모든 \( F \)값을 정확히 측정해내기는 불가능하다.

두 정수 \( N, K \)가 주어졌을 때 가능한 모든 \( F \)의 값에 대해 정확히 측정해내기 위한 최소 테스트 횟수를 출력하시오.

첫째 줄에 정수 \( N(1≤N≤10^{100}) \)이 주어진다.

둘째 줄에 정수 \( K(1≤K≤N) \)가 주어진다.

첫째 줄에 정확한 측정을 위해 필요한 최소 테스트 횟수를 출력한다.