1351번: 무한 수열

1351번: 무한 수열 - DP

N, P, Q가 주어질 때,

A[0] = 1

A[i] = A[i/P] + A[i/Q]

인 점화식을 만족하는 A[N]을 구하는 문제이다.

이와 같이 간단한 점화식은 중복되는 부분문제를 저장하는 DP기법을 사용하려고 접근하지만

N이 최대 10^12이기에 부분문제를 저장하는 배열을 선언할 수 없다.

그러나 점화식을 자세히 보면 i가 계속 P, Q로 나누어지는데

P와 Q가 최소값인 2일 때에도 2^40 >= 10^12이기에 각각 40보다 많은 항을 보지 않는 것을 알 수 있다.

이에 부분문제를 담는 배열을 지수에 대한 값을 인자로 두어

dp[41][41]와 같이 표현한 뒤 점화식을 세워 문제를 풀 수 있다.

또다른 방법으로는 적은 값만 참조하기에 map을 이용하여

value값이 0이라면 값을 업데이트 해주고 아니라면 그 값을 가져다 쓰는

전형적인 재귀적 동적 계획법을 사용하여 풀 수 있다.