백준] 1351 - 무한 수열

시간 제한 : 2초

메모리 제한 : 128MB

입력

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

출력

첫째 줄에 A_N을 출력한다.

소스코드

#include <map>
#include <iostream>
using namespace std;

map<long long, long long> dp;
long long recursive(long long N, long long& P, long long& Q)
{
	if (N == 0)
		return 1;
	else if (dp[N])
		return dp[N];

	return dp[N] = recursive(N / P, P, Q) + recursive(N / Q, P, Q);
}
int main(void)
{
	long long N, P, Q;

	cin >> N >> P >> Q;

	cout << recursive(N, P, Q);
}

Tip

일반적으로 DP(동적계획법, 다이나믹) 문제를 풀 때는 배열을 이용하지만, 이 문제는 배열을 사용하지 않는다. 문제 조건 상, 배열을 최대 10^12까지 배열을 생성해서 만들 수도 없을 뿐더러, 만들 필요도 없다. 따라서 맵(map)을 이용해서 필요한 구간만 구하는 방법으로 접근한다.