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

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

1354번: 무한 수열 2

 

 

[난이도] Gold4
[유형] DP

[풀이]
map을 이용해 메모제이션을 해주면 long long 형의 큰 수도 저장할 수 있습니다.
i/P, i/Q와 같이 P,Q로 나눈 후의 수들만 필요하기 때문에 너무 많은 수가 저장되는 것을 저장할 필요가 없습니다.

 

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

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1354.cpp