이동식 저장소

그러게 몇 번 나누어질까? 1407번: 2로 몇 번 나누어질까 자연수 N이 주어지면, 자연수를 유지하면서 N을 2로 몇 번까지 나눌 수 있는지를 생각해 볼 수 있다. 즉, N의 모든 약수 중 2의 거듭제곱 꼴이면서 가장 큰 약수를 생각하는 것이다. 예를 들어 15의 www.acmicpc.net 입력 범위를 보아하니 선형으로 탐색하면 절대 안 된다. 이런 경우에는 규칙이 있을 거라는 강력한 믿음을 갖고 문제를 바라보자. 문제에서 제시한 ``N의 모든 약수 중 2의 거듭제곱 꼴이면서 가장 큰 수``를 $f(N)$으로 정의하자. 규칙을 찾기 위해 $N \le 50$까지의 $f(N)$을 출력해 보면 다음과 같다. 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 ..