1407. 2로 몇 번 나누어질까

그러게 몇 번 나누어질까?

1407번: 2로 몇 번 나누어질까

---

입력 범위를 보아하니 선형으로 탐색하면 절대 안 된다. 이런 경우에는 규칙이 있을 거라는 강력한 믿음을 갖고 문제를 바라보자.

 

문제에서 제시한 ``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 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2

보아하니 4개씩 끊어서 보면 좋을 것 같다. 범위를 늘려서 $N \le 128$까지의 $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 4
1 2 1 32
1 2 1 4
1 2 1 8
1 2 1 4
1 2 1 16
1 2 1 4
1 2 1 4
1 2 1 4
1 2 1 8
1 2 1 16
1 2 1 4
1 2 1 4
1 2 1 32
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 4
1 2 1 128

눈에 띄는 것은 ``1 2 1 T``의 꼴이 반복된다는 점. 4의 배수 자리에 오는 값만 어떻게 하면 될 것 같다. 일단 규칙이 있는 것 같으니 구하는 값을 수식으로 나타내 보자. $F(N)=f(1)+f(2)+\cdots+f(N)$으로 정의하면 구하는 정답은 $F(B)-F(A-1)$이다.

 

4의 배수 자리의 값만 따로 떼어 보자.

4 8 4 16 4 8 4 32 4 8 4 16 4 8 4 64

나는 이 값들을 10분간 째려본 결과 아주 흥미로운 결과를 알아냈다. 위의 값을 4로 나누면 우리가 처음에 구한 $f(N)$의 배열과 정확히 똑같아진다.

1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 

따라서 4의 배수 자리에 오는 값들을 $f(k)$꼴로 계산할 수 있다. $k$를 ``N보다 크지 않은 값 중 가장 큰 4의 배수``로 정의하면 $F(N)$을 다음과 같이 구할 수 있다.

 

$F(N) = k + F(N \mod 4) + 4F(\frac{k}{4})$

 

• 첫 번째 항 $k$는 반복적으로 나타나는 ``1 2 1``의 합이다. 반복되는 패턴이 $\frac{k}{4}$번 나타나므로 이 값들을 모두 더하면 $(1+2+1) \times \frac{k}{4}=k$이다.
• 두 번째 항 $F(N \mod 4)$는 $\sum_{i=k+1}^{N}{f(i)}$이다. $N$이 4의 배수가 아닐 수도 있기 때문에 뒤에 남는 값들을 더해줘야 한다.
• 세 번째 항 $4F(\frac{k}{4})$는 4의 배수 자리에 오는 값을 더한 결과이다. 위에서 보았듯이 4의 배수 자리에 오는 값들을 4로 나누면 원래의 수열과 정확히 일치한다.

이렇게 하면 $F(N)$을 $log_{4}{N}$ 시간에 구할 수 있다. 

---

재귀 호출하는 부분이 인상적인 문제. 나는 개인적으로 매우 아름다운 문제라고 생각한다.