백준 1351 무한 수열 (C++)

1351번: 무한 수열

dp를 이용한 문제이다. N의 범위를 보면 int의 범위를 넘기때문에 자료형을 long long으로 해주었다. 기존 dp에서는 최대 범위만큼 배열을 만들어 저장해주었지만 범위가 크기때문에 map을 이용하여 저장해주었다. 재귀를 통해 m[N]을 구해 출력해주었다. 쉽게 풀 수 있었던 문제였다.

#include <iostream>
#include <map>

using namespace std;

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

long long findResult(long long n) {
    if (m[n] != 0) return m[n];

    return m[n] = findResult(n / P) + findResult(n / Q);
}

void solution() {
    m[0] = 1;
    cout << findResult(N);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> P >> Q;

    solution();

    return 0;
}