백준 g5 1351 무한 수열 c++

https://www.acmicpc.net/problem/1351

1351번: 무한 수열

 

문제

• A0 = 1
• Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1)

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

 

풀이

N<= 10^12로 엄청 크므로 그냥 배열을 사용해서는 풀 수가 없다.

무한 수열 A를 구할 때 실제로 i=0~10^12를 모두 사용하는 게 아니다. 왜냐하면 P, Q >=2 이므로 i/2~i까지의 값은 구할 필요가 없다. 필요한 수만 저장할 수 있는 map을 사용해서 해결할 수 있다.

   ex. P=2, Q=3일 때 A7도 A3까지만 계산하면 됨

map은 값이 지정되지 않은 경우에는 default값으로 0을 넣어서 계산한다.

 

전체 코드

/*boj g5 1351 무한 수열*/
#include <iostream>
#include <unordered_map>
using namespace std;

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

long long dfs(long long n) {
    if (map.find(n) != map.end())
        return map[n];
    else
        return map[n] = dfs(n / P) + dfs(n / Q);
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> P >> Q;
    map[0] = 1;

    cout << dfs(N) << "\n";
}