# [Gold I] 골롱 수열 [문제 링크](https://www.acmicpc.net/problem/2038) ## 문제 설명 <p>Golomb 수열이란 모든 k에 대해 k가 수열상에서 f(k)번 등장하는 단조증가 수열이다. 단조증가 수열이란 k값이 증가함에 따라 f(k)값이 감소하지 않는 수열을 말한다. 여기서 k와 f(k)는 모두 자연수이다.</p> <p>골롱 수열은 유일하게 결정될 수밖에 없다. 잘 생각해 보시길 ..</p> <p>n이 주어졌을 때 f(n)을 구하는 프로그램을 작성하시오.</p> ## 입력 <p>첫째 줄에 n이 주어진다.</p> ## 출력 <p>첫째 줄에 f(n)을 출력한다.</p> ## 풀이 #### 이번에 골롱 수열이라는 것을 처음 알게 되어 어떤 수열인지 찾아보았습니다. 이 문제를 해결하기 위해 각각의 수의 개수가 f(1), f(2), ... , 개라는 것을 이용해 수를 누적해 풀었습니다. ``` c++ #include<bits/stdc++.h> using namespace std; const int MAX = 10'000'000; int f[MAX]; int solve(int n) { if(n==1) return 1; if(n<=3) return 2; f[1]=1; f[2]=f[3]=2; int cur=3, sum=3; while(sum<n) { if(sum+f[cur]<MAX) { for(int i=1;i<=f[cur];i++) { f[sum+i] = cur; } } sum += f[cur]; cur++; } return cur-1; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; cout << solve(n); } ```