[BOJ 1351] 무한 수열

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

본문

무한 수열 A는 다음과 같다.

• A₀ = 1
• A_i = A_⌊i/P⌋ + A_⌊i/Q⌋ (i ≥ 1)

N, P와 Q가 주어질 때, A_N을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 3개의 정수 N, P, Q가 주어진다.

출력

첫째 줄에 A_N을 출력한다.

제한

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

• 0 ≤ N ≤ 10¹²
• 2 ≤ P, Q ≤ 10⁹

---

풀이

$A$라는 값들을 모두 저장해둔다면 매우 쉽게 구현할 수 있을 것 같다. 그런데 $N$의 범위가 심상치 않다. $N \leq 10^{12}$이므로 $A$의 모든 값을 저장하는 것은 불가능하다. 그렇다면 우선 문제에 충실하게 생각해보자.

$P, Q \geq 2$이므로, $N$이 아무리 크더라도 계산해야하는 $A_i$의 개수는 생각보다 적음을 알 수 있다. 연산을 1번 진행할 때마다 계산해야하는 $i$가 반 이상 줄어든다. $2^{39} < 10^{12} < 2^{40}$이므로, $N = 10^{12}$이더라도 쪼개는 연산은 최대 40번 정도만 진행하면 된다. 즉, 계산해야할 $A_i$ 항의 수는 생각보다 적으니 구현해보자!

계산 결과를 저장해두는 저장장치를 하나 생각하자. $A_i$가 계산되어있다면 반환해주고, 계산되어있지 않았다면 $A_i = A_{\lfloor i / P \rfloor} + A_{\lfloor i / Q \rfloor}$를 계산하고 저장장치에 저장해주면 된다. 이 과정은 분할정복 알고리즘 + 다이나믹 프로그래밍 문제의 형식을 띠고 있다. 다만 아까 얘기했듯이, $N$의 범위가 매우 크므로 기존의 배열을 이용한 DP는 불가능하다. 원래라면 map을 사용해야겠지만, C에는 그런 것은 없으니 연결리스트를 사용하여 가변길이를 구현하고, 계산된 결과를 반환하는 것은 연결리스트를 전체 순회하며 찾아가기로 하자. 저장될 항의 수가 꽤 적으므로 전체 순회하여 답을 찾아도 크게 문제되지는 않는다. 사용되는 알고리즘이 많아서 그렇지, 분할정복 + DP 문제의 기본형같은 느낌이라 쉽게 구현할 수 있다.

소스코드

Github Link : Source Code

참고 알고리즘 : 분할정복 알고리즘, 다이나믹 프로그래밍, 연결리스트