[백준] 1351번 - 무한 수열 (C++) 문제 및 풀이

문제) 백준 - 동적 계획법(Dynamic Programming) - 무한 수열

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

1351번: 무한 수열

 

 

친절(?)하게도 점화식이 주어졌다. N의 범위가 10^12까지이므로 배열로 memoization 하는 것은 불가능하다. 또한 N이 P와 Q로 계속 나누어지기 때문에 10^12까지 인덱싱 하는 것은 비효율적이다. 따라서 map을 이용하여 memoization을 통해 기존 Top-down 방식의 Dp를 구현했다.

 

 

C++ 소스코드)

 

	#include <bits/stdc++.h>
	#define endl "\n"
	#define ll long long
	#define INF 987654321
	#define MAX 52
	#define MOD 1000000000
	using namespace std;
	typedef pair<int, int> p;
	ll P, Q;
	map<ll, ll> cache; //idx, val
	ll solve(ll n) {
	//기저 사례
	if (n == 0)return 1;
	ll& ret = cache[n];
	if (ret != 0)return ret;
	return ret = solve(n / P) + solve(n / Q);
	}
	int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	ll N;
	cin >> N >> P >> Q;
	cout << solve(N) << endl;
	return 0;
	}

view raw 1351.cpp hosted with ❤ by GitHub