Golomb sequence

문제 >

수학자 솔로몬 골롬(Solomon Golomb)의 이름을 붙인 골름 수열(Golomb sequence)은 단조 증가하는 정수의 수열 G(n) (n = 1,2, ...)으로서 숫자 n이 정확하게 G(n)번 나타나는 수열이다. 예를 들어, n= 20까지의 G(n)은 다음과 같다.

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
G(n)	1	2	2	3	3	4	4	4	5	5	5	6	6	6	6	7	7	7	7	8

골롬 수열은 G(1) = 1부터 시작하는 자체 생성하는(self-generating) 수열의 한 종류로서 다음과 같은 방법으로 수열에 속하는 숫자들을 차례로 생성한다.

1. G(1) = 1이고 수업의 정의에 의하여 1은 1번만 나타나야 하므로 수열에서 다음에는 숫자 2가 나타나야 한다. 즉, G(2) = 2여야 한다.
2. G(2) = 2이므로 수열의 정의에 의하여 2는 2번만 나타나야 한다. 따라서 G(3) = 2이고 G(4) = 3여야 한다.
3. G(3) = 2이므로 수열의 정의에 의하여 3은 2번만 나타나야 한다. 따라서 G(5) = 3이고 G(6) =4여야 한다.
4. 이와 같은 방법으로 수열에 속하는 다음 숫자를 반복적으로 생성한다.

어떤 정수 n 이 주어졌을 때, 골롬 수열에서 G(n)을 계산하는 프로그램을 작성하시오.

 

입력 >

입력은 표준입력(standard input)을 사용한다. 입력은 t 개의 테스트 케이스로 주어진다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t가 주어진다. 두 번째 줄부터 t 개의 줄에는 한 줄에 한 개의 테스트 케이스에 해당하는 정수 n(1 <= n <= 1,000)이 주어진다. 잘못된 데이터가 입력되는 경우는 없다.

 

출력 >

출력은 표준출력(standard output)을 사용한다. 입력되는 테스트 케이스의 순서대로 다음 줄에 이어서 각 테스트 케이스의 결과를 출력한다. 각 테스트 케이스에 해당하는 출력의 첫 줄에 입력되는 정수 n에 해당하는 골롬 수열의 G(n)을 출력한다.

 

입출력 예시

입력	출력
3 1 16 1000	1 7 86

---

골롬 수열이 뭔지 이해하는데 꽤 어려웠다.

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
G(n)	1	2	2	3	3	4	4	4	5	5	5	6	6	6	6	7	7	7	7	8

G(1)= 1이고, G(1)이 1이니까 골롬 수열에서는 1이 한번 나타나야 한다는뜻이다. 즉 G(2)는 2가 된다.

그럼 G(2)= 2이므로, 골롬 수열에서는 2가 2번 나타나게 된다. 즉 G(3)= 2가 된다. 

그럼 G(3)=2 이니까, 골롬 수열에서 3이 2번 나타나야 한다. 즉 G(4) = 3, G(5) = 3 이 된다. 

이런 식으로 수열을 반복적으로 생성한다.

 

근데 골롬 수열에 대해 찾아보니까 점화식이 존재했다.

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

 

그래서 G(1) = 1 로 첫 값만 지정해 두고 반복문 돌렸다.

그리고 찾은 새로운 특성이 있었는데 sum에 계속해서 골롬 수열의 f(i)값을 더하다가 sum이 n을 넘으면 그때의 i값이 n일때 G(n)의 값이 된다는 점이다. 

그래서 적용시켜줬다.

 

반응형

int map[1001]; //golomb 수 저장

// G(n+1) = 1 + G(n + 1 - G(G(n)))
int golomb(int n) {
    int sum =1;
    int i;
    for(i=2;i<=n;i++){
        map[i] = 1 + map[i - map[map[i-1]]];
        sum += map[i];
 
        // sum에는 계속해서 골롬 수열의 f(i)값이 담기고 있고 결국 sum이 n을 넘으면
        // 그때 i값이 n일때 f(n)의 값이 된다.
        if (sum >= n){
            break;
        }
    }
    return i;
}

문제 해결 끝.

점화식이 존재하는지 몰랐으면 아주 골치아플 뻔 했다.

골아파덕