백준[1351번] 무한수열 C++

 

https://www.acmicpc.net/problem/1351

1351번: 무한 수열

 

해당 문제는 dp와 hash를 적용하여 문제를 해결하였다,

 

처음에, dp만을 활용하여 재귀함수 호출을 통해서 문제를 제출했으나, 시간 초과가 발생하였다. 아무래도 n <= 10^ 12, p, q <= 10^9이다보니, memorization을 활용하지 않아서 그런 것 같다.

* 해당 문제는 Top-down 방식으로 dp를 해결하다보니 memorization이 필요하다.

따라서 map STL 라이브러리를 사용하여 해결하는데, 해당 문제에서 dp의 순서는 크게 상관없기때문에 상대적으로 더 간단한 unordered_map을 활용한다. 또한 배열로 선언하기에는 n이 너무 크므로, map을 활용하여 필요한 값들만 따로 저장해두므로 훨씬 편리하다.

또한, 

A[0] = 1

A[i] = A[i/p] + A[j/q] 이므로 다음과 같이 코드를 작성하였다.

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

long long n, p, q;
long long res = 0;
unordered_map<long long, long long> m;

long long solution(long long x)
{
    if (x == 0)
        return 1;

    if (m[x] != 0)
    {
        return m[x];
    }
    else
    {
        return m[x] = solution(x / p) + solution(x / q);
    }
}

int main(int argc, char const *argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> p >> q;

    m[0] = 1;
    cout << solution(n);

    return 0;
}