[Algorithm]Baekjoon 1351번 :: 무한 수열

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

1351번: 무한 수열

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
long long n;
int p, q;
unordered_map<long long, long long> dp;
 
long long GetAnswer(long long num)
{
    if (dp[num] != 0) return dp[num];
 
    long long result = GetAnswer(num / p) + GetAnswer(num / q);
    
    return dp[num] = result;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> p >> q;
 
    dp[0] = 1;
 
    cout << GetAnswer(n) << endl;
}

 

아주 스탠다드한 유형의 dp문제이다. n값이 최대 1조까지 들어올 수 있으니, 그부분만 유의해서 작성하면 된다.

n값이 크다보니 dp컨테이너를 배열로하면 메모리초과니까 map을 이용해보도록 하자.