[백준 1351번] [Map / DP] 무한 수열

Approach

Top-down 방식으로 DP를 짜면 중복되는 계산을 줄이면서 계산을 할 수 있을 것이라는 느낌이 든다.

추가적으로 N이 매우 큰 상황이므로, 기존의 DP처럼 메모리를 미리 확보하고 저장하는 방식을 채택할 수 없고 Map 자료 구조를 활용해서 기존의 연산을 수행했는지 여부를 확인해주면 된다.

 

1. 기존에 연산을 수행한 값 : 메모이제이션을 사용. 즉 Map에서 value값을 그대로 읽어주면 된다.

2. 기존에 연산을 수행하지 않은 값 : Top-down을 활용하여 구해준 뒤, Map에 저장해주면 된다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
typedef long long ll;
map<ll, ll> s;
ll n, p, q;

ll s_value(ll v){
    if(s.find(v) == s.end()) return s[v] = s_value(v / p) + s_value(v / q);
    else return s.find(v) -> second;
}

int main(void){
    fastio;
    cin >> n >> p >> q;
    s[0] = 1; // Default value
    cout << s_value(n) << "\n";
    return 0;
}