시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 250 | 86 | 76 | 39.378% |
치삼이는 정사각형의 종이 하나를 가지고 있다. 종이를 정확히 반으로 여러 번 잘라 같은 크기를 가진 종이를 N개 가지고 싶다.
치삼이는 종이 크기의 종류가 두 가지가 넘으면 복잡해서 머리가 아프다. 따라서 치삼이가 자른 종이 크기의 종류는 두 가지를 넘을 수 없다.
위의 주어진 그림의 종이에 붙여진 숫자는 종이 크기의 종류를 의미한다. 같은 숫자가 붙은 종이는 같은 크기이다.
가장 오른쪽 그림은 치삼이가 가지고 있는 종이 크기의 종류가 2가지를 넘어가서 치삼이가 머리가 아프다.
종이는 한 번에 하나의 종잇조각만을 자를 수 있다. 겹치거나 종이를 나란히 놓아 여러 개의 종잇조각을 한 번에 자를 수 없다.
같은 크기의 종이를 최소 N개 얻고 싶을 때, 치삼이가 종이를잘라야 하는 횟수의 최솟값을 구해보자.
치삼이가 필요한 종이의 개수 N이 주어진다. N은 양의 정수이다. (1 ≤ N < 232)
종이를 자르는 최소 횟수를 출력한다.
13
14
13개의 같은 크기의 종이를 얻기 위해서는 14번 잘라 위의 그림과 같은 결과를 얻게 된다.
2가 붙은 종이 14개로 최소 13개의 같은 크기의 종이를 얻을 수 있다.
University > 가톨릭대학교 > 제1회 가톨릭대학교 프로그래밍 경진대회 (CCPC) > Div. 2 1번