1351번: 무한 수열 (acmicpc.net)

##
dp문제로 탑다운 방식으로 풀면 된다
N값이 매우 커서 그냥 표 채우는 식으로 풀수는 없다.

##
#include<iostream>
#include<bits/stdc++.h>
#include<map>

using namespace std;

long long N,P,Q;
map<long long, long long> map1;


long long func2(long long n){
    if (map1.count(n)) return map1[n];
    return map1[n] = func2(n/P) + func2(n/Q);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin >> N >> P >> Q;
    map1.insert({0,1});

    cout << func2(N);

    return 0;
}


## map 사용예제
#include<iostream>
#include<bits/stdc++.h>
#include<map>

using namespace std;

long long N,P,Q;
map<long long, long long> map1; // <key,value>


long long func2(long long n){
    if (map1.count(n)) return map1[n];
    return map1[n] = func2(n/P) + func2(n/Q);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin >> N >> P >> Q;
    map1.insert({0,1});

    cout << func2(N) << "\n";

    if(map1.find(1) != map1.end()){ //데이터를 끝까지 찾지 못할경우 iterator는 map.end() 반환
        cout << "find"<< '\n';
    }
    else{
        cout <<"not find"<<'\n';
    }
   
    //인덱스기반 순회
    for (auto iter=map1.begin();iter != map1.end();iter++){
        cout<< iter->first << " " << iter->second << endl;
    }


    // 범위기반 순회
    for (auto iter:map1){
        cout << iter.first << ' ' << iter.second << endl;
    }
   

    return 0;
}
파이썬으로 풀면 그냥 풀었을것 같기도 하고
cpp로 먼저 시도하다보니 새로운걸 봐서 적어둔다


##
C++ 표준 라이브러리에서 제공하는 std::map과 std::unordered_map은 각각 다른 방식으로 키를 찾습니다. 따라서 두 자료구조의 시간복잡도도 다릅니다.

std::map:std::map은 내부적으로 균형 이진 탐색 트리(주로 레드-블랙 트리)를 사용하여 구현됩니다.
키를 찾는 연산(탐색, 삽입, 삭제)의 시간복잡도는 O(logn)입니다.
이는 트리의 높이에 비례하며, 삽입과 삭제 연산도 O(logn) 시간이 소요됩니다.


std::unordered_map:std::unordered_map은 내부적으로 해시 테이블을 사용하여 구현됩니다.
키를 찾는 연산의 평균 시간복잡도는 O(1)입니다.
최악의 경우(해시 충돌이 모두 발생하여 하나의 버킷에 몰리는 경우)에는 O(n) 시간이 소요될 수 있지만, 이는 매우 드문 경우입니다.
삽입과 삭제 연산도 평균적으로 O(1) 시간이 소요됩니다.

따라서, std::map을 사용할 때는 키를 찾는 연산이 O(logn)의 시간복잡도를 갖고, std::unordered_map을 사용할 때는 평균적으로 O(1)의 시간복잡도를 갖습니다.