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

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

1351번: 무한 수열

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

ll N, P, Q;
map<ll, ll> m; //시간초과 방지

ll func(ll n)
{
    if(n==0) return 1;
    if(m[n]) return m[n]; //map에 값이 있으면 바로 return (중복방지)
    return m[n] = func(n/P) + func(n/Q);
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

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

    return 0;
}

피보나치 수열을 재귀로 풀때와 유사한 방법으로 풀 수 있는 문제이다.

N의 범위가 굉장히 크기에 long long으로 선언해주어야 하고, 이로인해 반복문을 이용한 Bottom-up 방식으로 풀이가 불가능하기에 재귀를 이용한 Top-down 방식으로 구현해주어야 한다.

 

이때 피보나치 수열을 구현할때와 같이 바로 계산을 해준다면 중복되는 값들도 같이 계산하게 되어 시간초과가 발생한다.

이를 방지하기 위해 map을 사용해주고, map에 값이 있다면 바로 출력하도록 하여 중복 계산을 방지해준다.