[2038번] 골롱 수열

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Map STL :: http://www.crocus.co.kr/604

2. 골롱 수열 :: https://en.wikipedia.org/wiki/Golomb_sequence

3. 점화식 :: http://stackoverflow.com/questions/12786087/golombs-sequence

골롱 수열에 대한 이해자체가 처음에는 좀 어려웠는데 여기서 골롱 수열이 무엇인지 말해보고자 한다.

우선 골롱 수열의 정의는 다음과 같다.

각 k에 대해 k라는 숫자가 정확하게 f(k)번 등장하는 단조 증가 수열을 골롱 수열이라 한다.

골롱 수열을 잠깐 나열해본다면 다음과 같다.

k   :: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 

f(k) :: 1, 2, 2, 3, 3, 4, 4, 4, 5, 5,  5

즉, 1은 f(k)에서 1개 있고, 2는 f(k)에서 2개 있고, 3은 f(k)에서 2개 있고, 4는 f(k)에서 3개 있고... 를 반복한다.

이 문제를 위해 구글링을 해본 결과 점화식이 존재했다.

G(1) = 1
G(n+1) = 1 + G(n + 1 - G(G(n)))

골롱 수열에 대한 점화식인데 가장 간단한 방법은

for(int i = 2; i <= n ; i ++)

{점화식}

cout << n번째 점화식 값 << endl; 을 해주면 정답이지만, 

n이 20억이기에 for문을 20억번 돌리는 것은 무리가 있다.

따라서 점화식을 이용하되 조금 변형해서 생각해봐야 한다.

sum이라는 변수를 두고 i번째의 f(i)를 계속해서 더해준다.

이 의미는 sum이 n보다 같거나 커지는 순간의 i가 n에 해당하는 f(n)값이 된다는 의미이다.

예를들어 n = 10일때 f(10)은 5이다.

그 이유는 i가 1일때부터 더해온다면 1 + 2 + 2 + 3 + 3 >= 10이 되고,

1 + 2 + 2 + 3 + 3의 의미는 1이 1번, 2가 2번, 3이 2번, 4가 3번, 5가 3번인데

총 수열의 길이가 11이 되는 동안 5에 머물고 있었다는 것이다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <map>
 
using namespace std;
 
map<long long, long long> mp;
 
int main()
{
    long long n;
    long long sum = 0;
    scanf("%lld", &n);
 
    if (n == 1)
    {
        cout << 1;
        return 0;
    }
 
    mp[1] = 1;
    sum += mp[1];
 
    long long i;
    for (i = 2; i <= n; i++)
    {
        // 골롱 수열 점화식 
        mp[i] = 1 + mp[i - mp[mp[i - 1]]];
        sum += mp[i];
 
        // sum에는 계속해서 골롱 수열의 f(i)값이 담기고 있고 결국 sum이 n을 넘으면
        // 그때 i값이 n일때 f(n)의 값이 된다.
        if (sum >= n)
            break;
    }
 
    cout << i << endl;
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>