[백준] 1351 무한 수열

문제

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

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

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

입력

첫째 줄에 3개의 정수 N, P, Q가 주어진다.

출력

첫째 줄에 AN을 출력한다.

 

똑같은 A[i]를 여러번 계산해야할 수 있으므로, 이를 막아주는 메모제이션 즉 DP를 사용합니다.

 

DP(int k){

     만약 A[k]가 존재한다면 return  A[k]

     그게 아니라면 return DP(k/P) + DP(k/Q)

}

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 };
ll N, P, Q;
unordered_map<ll,ll>um;
ll n(ll k) {
	if (um[k])return um[k];
	return um[k] = n(k / P) + n(k / Q);
}
int main() {
	FAST;
	cin >> N >> P >> Q;
	um[0] = 1;
	cout << n(N);

}