\(N\)층짜리 건물과 \(K\)개의 똑같은 달걀이 있다. 어떤 임계층 \(f\) (\(0 \le f \le N\))가 존재하여, \(f\)층보다 높은 곳에서 떨어뜨린 달걀은 깨지고 \(f\)층 이하에서 떨어뜨린 달걀은 깨지지 않는다. (모든 달걀의 강도는 같다.)

달걀을 어떤 층에서 떨어뜨려 깨지지 않으면 그 달걀을 회수해 다시 사용할 수 있고, 깨지면 그 달걀은 사라진다. 우리는 임계층 \(f\)의 정확한 값을 반드시 알아내고 싶다.

최악의 경우에도 임계층을 확실히 알아내기 위해 필요한 최소 시도(떨어뜨리기) 횟수를 구하여라.

\(1 \le K \le 100\), \(1 \le N \le 10\,000\).

첫째 줄에 두 정수 \(K\)와 \(N\)이 공백으로 구분되어 주어진다.

최악의 경우에도 임계층을 알아내기 위한 최소 시도 횟수를 한 줄에 출력한다.

riseoj 작성

출처 Original