[BOJ 15717] 떡파이어

문제 링크 : https://www.acmicpc.net/problem/15717

문제

떡파이어의 불로장생의 비밀은 바로 떡국이다.

떡파이어는 떡국을 먹은 그릇의 개수만큼 나이를 먹는다. 그들은 매일 떡국을 먹는데, 떡국을 먹는대로 바로 소화가 가능하기 때문에 하루에 얼마든지 원하는만큼 떡국을 먹을 수 있다. 그러나 전에 떡국을 얼마나 먹었든지, 그들은 기구하게도 떡국을 하루라도 먹지 않으면 생을 마감하게 된다.

어느 날, 디디는 어떤 떡파이어가 N세로 생을 마감하기까지 어떤 생을 살아왔는지 알고 싶어서, 그의 나이를 먹는 과정의 경우의 수를 세려고 한다. 그렇지만, 떡파이어의 나이가 많을 수록 그 경우의 수는 무수히 많아지기 때문에 디디는 곤란해하고 있다.

그런 디디를 위해 N세로 생을 마감한 떡파이어가 나이를 먹는 과정의 경우의 수를 세는 프로그램을 작성해야 한다.

떡파이어의 나이는 0세부터 시작된다.

N이 3일때를 예로 들면,

• 첫째 날 3개, 둘째 날 0개
• 첫째 날 1개, 둘째 날 2개, 셋째 날 0개
• 첫째 날 2개, 둘째 날 1개, 셋째 날 0개
• 첫째 날 1개, 둘째 날 1개, 셋째 날 1개, 넷째 날 0개로

총 경우의 수는 4이다.

입력

정수 N이 주어진다. (0 ≤ N ≤ 10¹²)

출력

나이를 먹는 방법의 가짓 수를 10⁹ + 7로 나눈 나머지를 출력하시오.

제한

시간 제한	메모리 제한
1sec	128MB

---

풀이

$N$세로 생을 마감하기까지 매일 최소 한 그릇 이상의 떡국을 먹으며 나이를 먹는 모든 경우의 수를 구하는 문제다. 문제의 예시와 $N$의 변화에 따른 가짓수를 분석하면 다음과 같은 규칙성을 발견할 수 있다:

• $N=1$: (1) $\rightarrow$ 1가지 ($2^0$)
• $N=2$: (2), (1+1) $\rightarrow$ 2가지 ($2^1$)
• $N=3$: (3), (2+1), (1+2), (1+1+1) $\rightarrow$ 4가지 ($2^2$)
• $N=4$: 8가지 ($2^3$)

위 규칙을 통해 $N \ge 1$인 경우 가능한 가짓수는 $2^{N-1}$이 됨을 알 수 있다. 이는 수학적으로 정수 $N$을 순서가 있는 양의 정수들의 합으로 나타내는 분할(Composition) 문제의 개수와 동일하다.

\[Ways(N) = \begin{cases} 1 & (N=0) \\ 2^{N-1} \pmod{10^9+7} & (N \ge 1) \end{cases}\]

입력으로 주어지는 $N$의 범위가 최대 $10^{12}$에 달하므로, 단순히 2를 $N-1$번 곱하는 방식으로는 제한 시간 내에 해결할 수 없다. 따라서 분할 정복을 이용한 거듭제곱 알고리즘을 적용하여 $O(\log N)$의 시간 복잡도로 빠르게 계산해야 한다. 계산 과정에서 지수가 0보다 작은 경우(즉, $N=0, 1$)를 예외 처리하고, $10^9+7$로 나눈 나머지를 취하며 오버플로우 방지를 위해 long long 자료형을 사용한다.

소스코드

Github Link : Source Code

참고 알고리즘 : 분할 정복을 이용한 거듭제곱