백준 1354번 무한 수열 2[C++]

1. 개요

 안녕하세요? 이번에 풀었던 문제의 유형은 다이나믹 프로그래밍입니다. 문제 지문 설명은 단순하군요. 초기값을 주고 하위 수열 원소 두 개를 더해가면서 만드는 피보나치와 비슷한 형태를 가지네요. 피보나치수열은 재귀로 간단하게 구할 수 있습니다. 하지만 시간복잡도가 지수 스케일이라 입력값이 크면 시간제한 안에 구할 수 없습니다. 

 

 이 문제도 N이 1e13까지 주어지므로 단순 재귀로는 구하기엔 어려워보입니다. 그렇다고 배열을 선언해서 메모이제이션을 해보려고 해도 배열의 크기가 1e13까지 할당을 해야 하는데 메모리 제한을 우뚝 넘어서서 어렵네요. 어떤 방법으로 메오이제이션을 해야 하는지가 이 문제의 핵심으로 보입니다.

 

2. 문제 풀이

 i >= 1을 만족하는 정수 i에 대해서 A[i] = A[i / P - X] + A[i / Q - Y]를 통해 계산을 하는데요. A[i]를 구하기 위해서 i 이하의 모든 수열 정보를 저장할 필요가 없다는 사실을 어렵지 않게 알 수 있었습니다. 따라서 1e13 크기의 배열로 메모이제이션을 구현할 수 있다고 하더라도 값은 띄엄띄엄하게 존재하게 됩니다.

 

 사용하지 않는 배열 공간을 최소화하는 방법 중 하나는 해쉬를 사용하는 방법입니다. 해쉬로 구현하게되면 실제로 사용하는 데이터만을 할당받으므로 이전에 계산했던 데이터를 재사용할 수 있으므로 최적화가 가능하고 메모리 문제를 해결할 수 있습니다.

 

3. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

unordered_map<ll, ll> A;
ll n, p, q, x, y;

ll solve(ll cur) {
    if(cur <= 0) {
        return 1ULL;
    }

    if(A.find(cur) != A.end()) {
        return A[cur];
    }

    return A[cur] = solve(cur / p - x) + solve(cur / q - y); 
}

int main() {
    fastio(nullptr, false);

    cin >> n >> p >> q >> x >> y;

    cout << solve(n);    
}

 

4. 제출 결과

 

 이진 트리 자료구조인 map을 사용해 보았는데 시간 초과가 납니다. unordered_map을 사용해서 해결하시면 됩니다.