[BOJ/백준][Gold4] 1351 : 무한 수열 (C++)

www.acmicpc.net/problem/1351

1351번: 무한 수열

 

 

[난이도] Gold4

[유형] DP

 

[풀이]

dp[n] = dp[n/P]+dp[n/Q]

N 제한이 크므로 map을 이용한다.

#include <cstdio>
#include <map>
using namespace std;
using ll = long long;
ll N;
map<ll,ll> m;
int P,Q;
ll sol(ll n){
    if(n==0) return 1;
    if(m.find(n) != m.end()) return m[n];
    return m[n] = sol(n/P)+sol(n/Q);
}
int main(){
    scanf("%lld%d%d",&N,&P,&Q);
    printf("%lld",sol(N));
}

 

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1351.cpp