백준 2038번 골롱 수열

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

이 문제를 풀기 위해서는 우선 골롱수열을 이해해야합니다.

n	1	2	3	4	5	6	7	8	9
f(n)	1	2	2	3	3	4	4	4	5

i) n은 1일 때 f(n)=1로 시작합니다.

ii) n은 2일 때 f(n)=2이고 f(n)=2이기 때문에 3번째 인덱스까지 2가 저장됩니다.

iii) 3번째 인덱스까지 2가 저장되었으므로(2가 2번 출현) 4번째 인덱스에는 3이 저장됩니다.

iv) 3번째 인덱스가 2이므로 3도 2번 출현합니다. 따라서, 5번째 인덱스까지 3이 저장됩니다.

v) 5번째 인덱스까지 3이 저장되었으므로(3이 2번 출현) 6번째 인덱스에는 4가 저장됩니다.

vi) 4번째 인덱스에 3이 저장되어있으므로 8번째 인덱스까지 4가 저장됩니다.(4가 3번 출현)

vii) 이후 같은 원리로 진행

골롱수열 개념을 이해한다고 해도 문제를 접근하기가 쉽지 않기 때문에 저는 stackoverflow(https://stackoverflow.com/questions/12786087/golombs-sequence)에서 제시한 점화식을 참고해서 풀었습니다.

알고리즘은 아래와 같습니다.

1. 배열의 최대 크기는 0x7fffffffbyte이기 때문에 20억 인덱스까지 표시하기 위해서는 map을 써야합니다.

2. N=1이면 f(N)=1이므로 1을 출력합니다.

3. N>1이라면 2~N까지 반복문을 통해 각각의 숫자가 몇개 등장하는지 계산하고 sum 변수에 더해줍니다.

4. sum 변수에 저장된 값이 N을 초과한다면 N번째 인덱스에 해당 인덱스가 저장되었다는 것이므로 반복문을 탈출하면서 해당 인덱스를 출력해줍니다.

#include <iostream>

#include <map>

using namespace std;

 

map<long long, long long> visited;

int visited[10000000000];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

        //골롱 수열 초기값

        if (N == 1)

        {

                 cout << 1 << "\n";

                 return 0;

        }

 

        long long sum = 0;

        visited[1] = 1;

        sum += visited[1];

 

        for (long long idx = 2; idx <= N; idx++)

        {

                 //점화식(위키피디아 참고)

                 visited[idx] = 1 + visited[idx - visited[visited[idx - 1]]];

                 sum += visited[idx];

 

                 //반복문 탈출 조건

                 if (sum >= N)

                 {

                         cout << idx << "\n";

                         break;

                 }

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~