1351. 무한 수열

문제 링크

1351번: 무한 수열

 

풀이

필요 지식: 다이나믹 프로그래밍, 재귀, 해시

 

해답을 구하기 위해 이전 번째 항의 값을 이용하니 DP를 활용하는 게 옳아 보인다. 그러나 N이 최대 10¹²이고, 메모리 제한도 128 MB이므로 0~10¹²번째 항까지 일일이 저장해 가며 푸는 방법은 불가능하다. 그렇다면 필요한 값만 저장해 뒀다 써야 할 것 같은데, 어떤 방식으로 해결해야 할까?

 

0번째 항부터 구해나가지 말고, N번째 항부터 나눠가는 방식을 생각해 보자. 주어진 식에 \(i=N\)을 대입하면

$$A_{N}=A_{\lfloor N/P \rfloor}+A_{\lfloor N/Q \rfloor}$$

이다. 그리고 \(A_{\lfloor N/P \rfloor}\)와 \(A_{\lfloor N/Q \rfloor}\) 역시 다음과 같이 나타낼 수 있다.

$$A_{\lfloor N/P \rfloor}=A_{\lfloor \lfloor N/P \rfloor /P \rfloor}+A_{\lfloor \lfloor N/P \rfloor / Q \rfloor}$$

$$A_{\lfloor N/Q \rfloor}=A_{\lfloor \lfloor N/Q \rfloor /P \rfloor}+A_{\lfloor \lfloor N/Q \rfloor / Q \rfloor}$$

뭔가 피보나치 수열처럼 재귀로 해결할 수 있을 것 같다. 실제로 \(A_{0}=1\)을 base condition으로 두고, 위 식을 바탕으로 하여 재귀함수 구현이 가능하다.

 

다만 N의 값의 크기와, 재귀의 특성으로 인한 실행 시간을 생각해야 한다. 재귀는 특성상 같은 함수를 여러 번 호출하므로 실행 시간을 많이 잡아먹는데, 특히 N/P = N/Q면 같은 값을 여러 번 계산하게 되므로 더욱 비효율적이다.

 

동일한 값을 여러 번 연산함으로 인한 함수 호출을 막기 위해, 구한 값을 별도의 자료구조에 저장할 것이다. 각 i번째 항에 대한 값은 유일하고, 정렬도 딱히 필요하지 않으므로 unordered_map 컨테이너에 i를 key로 하여 값을 저장한다. 이러면 해시 자료구조인 unordered_map 특성상 시간 복잡도는 \(O(1)\)이므로 탐색 속도도 빠르다.

 

시간 복잡도

\(P, Q\)의 값은 최소 2이므로, \(N/P, N/Q\)의 값은 항상 \(N\)보다 작은 값을 가진다. 그러므로 \(N\)이 커질수록 재귀호출의 깊이는 로그함수적으로 증가한다. 따라서 재귀함수의 시간 복잡도는 \(O(\log{N})\)이며, 해시로 이미 계산한 값을 저장하므로 실제로는 더 줄어든다.

 

소스코드

#include <iostream>
#include <unordered_map>
using namespace std;

long long N, P, Q;
unordered_map<long long, long long> um;

// 문제 해결을 위한 재귀함수
long long solve(long long num) {
    if(um.find(num) != um.end()) {
        return um[num];
    }
    else {
        long long A1 = solve(num / P), A2 = solve(num / Q);
        um.emplace(num, A1 + A2);
        return A1 + A2;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N >> P >> Q;
    um.emplace(0, 1);
    
    cout << solve(N);
    return 0;
}