문제

문제 분석

Recursive call로 쉽게 풀 수 있다.
이때, 반복되는 계산이 존재할 것이므로, dp를 사용하면 된다.
피보나치에서 사용하는 기본적인 발상과 거의 같다.

다만, 큰 범위 내에서 듬성듬성 필요한 부분만 저장하고 재활용 해야하는 상황이므로, 단순히 Array를 쓰기보다는 Map을 써야한다.

알고리즘

• DP(Tabulation)

자료구조

• map

결과

• 풀이1: 9944ms
• 풀이2: 3724ms

풀이 1

#include <iostream>
#include <vector>
#include <cmath>
#include <map>
using namespace std;

int64_t N, P, Q, X, Y;

map<int64_t, int64_t> m;

int64_t GetAiRecursive( int64_t i )
{
    if ( i <= 0 )
        return 1;

    if ( m.find(i) != m.end() )
        return m[i];

    // i > 0 && first time 
    int64_t l = i/P - X;
    int64_t r = i/Q - Y;
    return (m[i] = GetAiRecursive(l) + GetAiRecursive(r));
}

int main( void )
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin >> N >> P >> Q >> X >> Y;

    cout << GetAiRecursive(N);

    return 0;
}

풀이 2

#include <iostream>
#include <vector>
#include <cmath>
#include <unordered_map>
using namespace std;

int64_t N, P, Q, X, Y;

unordered_map<int64_t, int64_t> m;

int64_t GetAiRecursive( int64_t i )
{
    if ( i <= 0 )
        return 1;

    if ( m.find(i) != m.end() )
        return m[i];

    // i > 0 && first time 
    int64_t l = i/P - X;
    int64_t r = i/Q - Y;
    return (m[i] = GetAiRecursive(l) + GetAiRecursive(r));
}

int main( void )
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin >> N >> P >> Q >> X >> Y;

    cout << GetAiRecursive(N);

    return 0;
}

Other

map은 red-black tree를 사용한다. 모든 조작에 O(logN)이 걸린다.
unordered_map은 hash table을 사용한다. 모든 조작에 O(1)이다.

따라서, 단순히 key를 통한 접근만 필요하다면 unordered_map이 대개 빠르다. (다만, collision이 많은 경우엔 실제 O(1)보다 느릴 수 있음을 유의하자)
반면, 정렬된 순서대로 전체를 조사하는 경우 map이 더 좋다.