치삼이의 종이 자르기
시간 제한1초메모리 제한1024 MB
정사각형 종이 하나를 반으로만 잘라 같은 크기 조각을 N개 이상 얻으려 할 때, 크기 종류를 두 가지 이하로 유지하면서 자르는 최소 횟수를 구한다.
문제
치삼이는 정사각형의 종이 하나를 가지고 있다. 종이를 정확히 반으로 여러 번 잘라 같은 크기를 가진 종이를 N개 가지고 싶다.
치삼이는 종이 크기의 종류가 두 가지가 넘으면 복잡해서 머리가 아프다. 따라서 치삼이가 자른 종이 크기의 종류는 두 가지를 넘을 수 없다.
위의 주어진 그림의 종이에 붙여진 숫자는 종이 크기의 종류를 의미한다. 같은 숫자가 붙은 종이는 같은 크기이다.
가장 오른쪽 그림은 치삼이가 가지고 있는 종이 크기의 종류가 2가지를 넘어가서 치삼이가 머리가 아프다.
종이는 한 번에 하나의 종잇조각만을 자를 수 있다. 겹치거나 종이를 나란히 놓아 여러 개의 종잇조각을 한 번에 자를 수 없다.
같은 크기의 종이를 최소 N개 얻고 싶을 때, 치삼이가 종이를잘라야 하는 횟수의 최솟값을 구해보자.
입력
치삼이가 필요한 종이의 개수 N이 주어진다. N은 양의 정수이다. (1 ≤ N < 232)
출력
종이를 자르는 최소 횟수를 출력한다.