[백준] 1351번 무한 수열

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

long long N, P, Q;
unordered_map<long long, long long> m;

long long solve(long long num){
    long long ret;
    if(m.find(num)!=m.end()){
        return m[num];
    }
    ret=solve(num/P) + solve(num/Q);
    m[num]=ret;
    return ret;
}

int main(){
    fastio;

    cin>>N>>P>>Q;
    m[0]=1;
    if(N==0)
        cout<<1;
    else
        cout<<solve(N/P)+solve(N/Q);
}

<참고>

https://allmymight.tistory.com/161

<풀이>

[메모이제이션]: 한 번 계산한 값을 저장해두고, 같은 계산이 필요할 때 다시 계산하지 않고 저장된 값을 사용하는 기법

중복 계산을 피하기 위한 기법임 

unordered_map: 키-값 쌍으로 데이터를 저장하는 해시 테이블 기반의 자료구조이다.

입력값을 키(Key)로 사용 → n, 계산 결과를 값(Value)로 사용 → fibo(n)의 결과

m[key] = value 형태로 간단하게 저장 가능, 같은 입력이 들어오면 저장된 값을 그대로 반환

 

m.find[num]: find-num이라는 키가 존재하면 해당 키를 가리키는 반복자 반환하고 없으면 m.end() 반환.

따라서 m.find(num) != m.end()는 num에 대한 결과가 이미 존재한다는 것