1351 무한 수열

문제 정의

무한 수열 A를 푸는 문제 입니다.

 - A[0] = 1;

 - A[i] = A[i/P] + A[i/Q] ( i>=1, i/P 또는 i/Q가 정수가 아닐 때는 가우스 기호를 이용한다. ( 가우스 기호, [3.4] = 3)

 - N, P, Q가 주어질 때, A[N]을 구하여라. ( ,  )

---

문제 풀이 - 1

이 문제는 전형적인 DP 문제입니다. 

피보나치 문제에서 DP[n] = DP[n-1] + DP[n-2] 의 점화식으로 n번째 값을 구하기 위해 이전에 계산한 n-1, n-2번째 값을 이용합니다.

하지만, 이 문제의 큰 문제는 N과, P,Q의 범위입니다. N의 범위가 커 변수에 모두 저장할 수 없습니다.

첫 번째로 생각한 방법은 STL의 map을 이용해 저장하는 방법입니다. 실제 10^12크기의 변수는 메모리 제한에 걸리니

실제 사용되는 양은 그렇게 많지 않아 map에 저장해 사용하면 가능할 것이라 생각했습니다.

---

소스코드 - 1

#include < stdio.h >
#include < map >
using namespace std;
typedef unsigned long long ull;
ull N, P, Q;
map < ull, ull > m;
ull dp(ull x) {
	if (x == 0)
		return 1;
	if (m[x] != 0)
		return m[x];
	return m[x] = dp((ull)x / P) + dp((ull)x / Q);
}
int main() {	
	scanf("%lld%lld%lld", &N, &P, &Q);
	printf("%lld\n", dp(N));
	return 0;
}

---

문제 풀이 - 2

 map을 이용하면 편리하게 문제를 금방풀 수 있었지만, 허무해서 다른 방법은 없을까 생각해봤습니다.

한 가지 떠오른 방법은 N으로부터 P와 Q가 나눠지기 때문에 나눠진 수를 이용하면 저장할 수 있겠다 싶었습니다.

즉, N에서 P를 1번 나눈 값은 N/P이고 P는 1번 나누었고, Q는 0번 나누었습니다. 

N에서 같은 p와 q번 P,Q를 나눈 값은 언제나 동일한 점을 알았고, 이를 이용해 다음처럼 구현할 수 있었습니다.

---

소스코드 - 2

dp의 크기는 P와 Q의 최소값인 2로 나눌때의 최대값, 즉 10^12 = 2^10^4 으로 약 40 이상으로 잡으면 됩니다.

 
#include < stdio.h >
typedef unsigned long long ull;
ull dp[50][50], N, P, Q;
ull solve(ull x, int p, int q) {
	if (x == 0)
		return 1;
	if (dp[p][q] != 0)
		return dp[p][q];
	return dp[p][q] = solve((ull)x / P, p + 1, q) + solve((ull)x / Q, p, q + 1);
}

int main() {
	scanf("%lld%lld%lld", &N, &P, &Q);
	printf("%lld\n", solve(N, 0, 0));
	return 0;
}