BOJ 2038 - 골롱 수열

문제

Golomb 수열의 임의의 항을 구하는 문제이다. Golomb 수열은 임의의 \(k\)에 대해 \(k\)가 수열상에서 \(f(k)\)번 등장하는 단조증가 수열이다.

\(1\le n \le 2,000,000,000\)일 때 \(f(n)\)을 구해야 한다.

풀이

수열의 정의대로 \(i\)를 증가시켜 정확히 \(f(n)\)을 구하려고 하면 \(n\)의 범위 때문에 메모리 초과가 난다.

Golomb 수열의 점화식은 아래와 같다.

\[f(n+1)=1+f(n+1-f(f(n)))\]

이 점화식을 사용해서 dp를 구성하면 된다.
이때 \(i\)번째에 대해 \(\sum{f(i)}\)개의 항이 결정된 상태이기 때문에 수열의 합이 \(n\)을 넘는 시점의 \(i\)가 \(f(n)\)의 값이 된다.

소스코드

#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>

using namespace std;
using pii=pair<int, int>;
using vi=vector<int>;
using lld=long long;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, filled, i;
    vi a(4000000, 0);
    cin>>n;
    i=1;
    a[1]=1;
    filled=1;
    while(filled<n){
      i++;
      a[i]=1+a[i-a[a[i-1]]];
      filled+=a[i];
    }
    cout<<i;
    return 0;
}

풀고나서

• 점화식을 스스로 구해보려고 했는데 어려웠다.