[C++] 백준 1351번: 무한 수열 - Recursion, DP

https://www.acmicpc.net/problem/1351

1351번: 무한 수열

 

A0는 1로 주어지고, Ai ~ An은 주어지지 않았다.

대신 점화식으로 Ai = Ai/p + Ai/q인데, p와 q 값이 난수이다.

그러므로 확정적으로 아는 값은 A0뿐이고, p와 q에 따라 Ai의 값이 변한다.

 

먼저 예제 1번을 가지고 규칙을 찾아보았다.

N = 7, P = 2, Q = 3의 입력이 주어졌을 때, Ai는 아래와 같다.

A0 = 1

A1 = A0 + A0 = 2

A2 = A1 + A0 = 3

A3 = A1 + A1 = 4

A4 = A2 + A1 = 5

A5 = A2 + A1 = 5

A6 = A3 + A2 = 7

A7 = A3 + A2 = 7

여기서 P로 나누어지는 수는 Ai/p로, i를 p로 나눈 몫이었고, Q로 나누어지는 수는 Ai/q로 역시 i를 q로 나눈 몫이었다.

 

그래서 생각한 접근은 재귀적으로 문제를 해결하는 것이었다.

쉽게 말해,

A7 = A3 + A2인데,

A3은 다시 A1 + A1으로 구할수 있고, A2는 A1 + A0으로 구할 수 있다.

다시 A1은 A0 + A0로 구해지므로 i값이 0이 아닌 경우 계속해서 p와 q로 나눈 수를 더해주면 된다.

 

그래서 세운 재귀식

#include <iostream>
using namespace std;
using ll=long long;
ll div(ll x, ll p, ll q){
    if(x==0) return 1;
    else return div(x/p, p, q)+div(x/q, p, q);
}
int main(){
    ll n, p, q, ans=0; cin >> n >> p >> q;
    if(!n){
        cout << 1;
        return 0;
    }
    ans=div(n/p, p, q)+div(n/q, p, q);
    cout << ans;
}

 

그런데 위 코드에서는 TLE가 발생했다.

그래서 dp로 접근하려고보니 범위가 10^12이었으므로, 배열이 아닌 map을 이용하여 수를 저장하도록 설계했다.

#include <iostream>
#include <map>
using namespace std;
using ll=long long;
map<ll, ll>dp;
ll div(ll x, ll p, ll q) {
    if(dp[x]) return dp[x];
    else return dp[x]=div(x/p, p, q)+div(x/q, p, q);
}
int main(){
    ll n, p, q, ans=0; cin >> n >> p >> q;
    dp[0]=1;
    ans=div(n/p, p, q)+div(n/q, p, q);
    if(!n) ans=1;
    cout << ans;
}