백준 1351번 무한 수열

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

범위가 long long인 것만 조심하면 간단히 풀 수 있는 DP 문제였습니다.

#include <iostream>

#include <map>

using namespace std;

 

long long N, P, Q;

map<long long, long long> cache;

 

long long func(long long N)

{

        if (cache.count(N))

                 return cache[N];

        else

                 return cache[N] = func(N / P) + func(N / Q);

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> P >> Q;

 

        cache[0] = 1;

        cout << func(N) << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~