[C/C++] 백준 - 1351번 : 무한 수열

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

1351번: 무한 수열

문제

무한 수열 A는 다음과 같다.

• A0 = 1
• Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1)

N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.

 

제한

• 0 ≤ N ≤ 10^12
• 2 ≤ P, Q ≤ 10^9

---

 

무한 수열을 구하는 문제이지만 점화식이 이미 제시되어있는 꼴로 보아 동적계획법으로 풀는 것이 가장 적합하다는 판단이 든다. 그리고 생각해야 할 것이 N과 P, Q 값 제한이 생각보다 크다.

 

메모이제이션을 해야하는데 이를 배열로 표현한다고 하면 메모리 내에 모든 값을 담아낼 수가 없다. 그래서 map을 이용해서 메모이제이션을 적용시켜야한다. 범위는 long long을 적용해야한다.

 

그 외 코드는 문제에 주어진 그대로 작성하면 된다.

 

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <climits>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1234567
#define endl '\n'
#define ENDL cout << endl

using namespace std;

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

void input() {
	cin >> N >> P >> Q;
}

ll path(ll n, ll p, ll q) {
	if (n == 0) return 1;
	ll& ret = m[n];
	if (ret != 0) return ret;
	return ret = path(n / p, p, q) + path(n / q, p, q);
}

ll solution() {
	return path(N, P, Q);
}

int main() {
	fastio;
	input();
	cout << solution() << endl;

	return 0;
}