백준 2038번 골롱 수열

문제

Golomb 수열이란 모든 k에 대해 k가 수열상에서 f(k)번 등장하는 단조증가 수열이다. 단조증가 수열이란 k값이 증가함에 따라 f(k)값이 감소하지 않는 수열을 말한다. 여기서 k와 f(k)는 모두 자연수이다.

골롱 수열은 유일하게 결정될 수밖에 없다. 잘 생각해 보시길 ..

n이 주어졌을 때 f(n)을 구하는 프로그램을 작성하시오.

문제풀이

사용한 알고리즘 : 수학

(0) 생각

 일단 Golomb 수열이 무엇인지 이해해야 합니다. 아래 링크 달겠습니다.

 Golomb 수열

 

 일단 i < j 에서 Golomb[i] <= Golomb[j] 입니다. ...(*)

 잘 생각해보면 Golomb[1] = 1 일 수 밖에 없습니다.

 Golomb[1] > 1 이면 예를 들어 Golomb[1] = 2 이면 1이 2번 나와야 한다는 소리인데,

 Golomb[1] = 2 인 시점에서 이후 index 에서 1이 나오면 (*) 에 모순이겠죠.

 조금 더 생각해보면 아래와 같이 Golomb 수열이 나온다는 걸 알 수 있습니다.

Index	1	2	3	4	5	6	7	8	9
Golomb	1	2	2	3	3	4	4	4	5

링크에 따르면 Golomb[n+1] = 1 + Golomb[ n+1 - Golomb[ Golomb[n] ] ] 입니다.

(1) 코드 14~21

 위에 생각을 써먹을 것입니다.

 각 index가 어디까지 채워지는 지를 생각합니다.

 위 표를 통해 보면, 

 1은 1까지 채워지고, 2는 3까지 채워지고, 3은 5까지 채워지고, 4는 8까지 채워지고... 입니다.