백준 - 1351 무한 수열

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

1351번: 무한 수열

 

map을 이용한 동적 계획법 문제이다.

그냥 동적 계획법을 사용하면 N으로 10의 12승만큼 잡아야 하기 때문에 메모리도 안되고 시간초과도 날 것이다.

 

 

 

 

#include <iostream>
#include <map>

using namespace std;
typedef long long ll;

int P, Q;
map<ll, ll> m;

ll getValue(ll N) {
    if(N == 0) return 1;
    if(m[N] != 0) return m[N];


    m[N] = getValue(N / P) + getValue(N / Q);
    return m[N];
}


int main() {
    ll N;
    cin >> N >> P >> Q;


    cout << getValue(N);

    return 0;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~