BOJ 1351: 무한 수열

#BOJ 1351: 무한 수열

1351번: 무한 수열

#풀이

이 문제는 피보나치 수열과 비슷한 문제이다.

 

ans = func(n) = func(n/q) + func(n/p) ... 형태로 함수를 만들어 사용하면 해결할 수 있다.

 

그냥 처음에는 재귀함수를 생각못하고 모든 숫자를 배열에 저장하면서 풀었다가 메모리초과가 떠서

#include<iostream>
#include<unordered_map>
using namespace std;
typedef long long ll;
ll n;
int p, q;
 unordered_map<ll, ll> v;

 ll func(ll x) {
	 if (x == 0)
		 return 1;
	 if (v[x]) return v[x];

	 v[x] = func(x / p) + func(x / q);
	 return v[x];
 }
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> p >> q;
	
	cout << func(n) << '\n';
	return 0;
}

힘들었다...

 

다시 복습을 해야할 것 같다...

 

#코드