[백준 1354번] 무한 수열 2 (C++)

문제링크 : https://www.acmicpc.net/problem/1354

1354번: 무한 수열 2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

ll N, P, Q, X, Y;
map<ll, ll>dp;

ll func(ll n)
{
    if(n<=0) return 1; //조건 1
    if(dp[n]) return dp[n]; //중복계산 방지
    else return dp[n] = func(n/P-X) + func(n/Q-Y); //조건 2
}
int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> P >> Q >> X >> Y;
    cout << func(N);

    return 0;
}

 

점화식 자체는 문제에 주어진 조건 그대로 구현을 해주면 된다.

해당 문제에서 문제점은 수의 범위가 굉장히 큰 것으로 단순히 배열로 선언이 불가능한 범위를 가진다.

따라서 이를 위해 map을 활용하여 값 할당 및 반환하였다.

당연하게도 계산에 관련된 값들은 long long으로 선언해주어야 한다.