[백준 2038번] 골롱 수열 (C++)

문제링크 : https://www.acmicpc.net/problem/2038

2038번: 골롱 수열

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int arr[2000001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int N;
    cin >> N;
    arr[1] = 1;
    
    int idx = 2;
    int sum = 1; //N이 1인 경우 더해준 상태

    while(sum < N)
    {
        arr[idx] = 1 + arr[idx - arr[arr[idx-1]]]; //공식
        sum += arr[idx];
        idx++;
    }
    cout << idx-1;
    return 0;
}

골롱 수열이 무엇인지 알아야 풀 수 있는 문제이다.

나도 골롱 수열이 뭔지 몰라서 따로 찾아봤다.

 

N만큼 F(N)이 등장하는 수열이다.

아래 간단한 예시를 보자.

N      : 1 2 3 4 5 6

F(N) : 1 2 2 3 3 4 4 4

 

초기값으로 F(1) = 1이고, 이후 2부터 보자.

F(2)은 2이고 2이기에 2번 반복된다. 

따라서 F(3)는 2이다.

 

F(3)은 2이기에 3이 2번 반복된다.

따라서 F(4~5)는 3이다.

 

F(4)는 3이기에 4가 3번 반복된다.

따라서 F(6~8)은 4이다.

 

이런식으로 수열이 반복되는 것을 볼 수있다.

 

골룽수열은 이미 점화식이 알려져있다.

초기값 : a(1) = 1;  
a(n+1) = 1 + a(n + 1 - a(a(n)))
-> a(n) = 1 + a(n - a(a(n-1)))

위 점화식을 이용하여 풀었고 n의 범위가 20억까지이기에 단순 반복문으로 하면 시간초과가 발생한다.

(1억당 1초 / 시간제한 2초)

그렇기에 각 arr[i]의 값을 sum에 더해주고, 이 sum이 N보다 크거나 같을 때 반복문을 종료하고 이때의 idx를 출력한다.