백준 문제풀이

BOJ 2038.cpp

#include <bits/stdc++.h>
using namespace std;
// https://en.wikipedia.org/wiki/Golomb_sequence
// Golomb[1] =1
// Golomb[n+1] = 1 + Golomb[ n+1 - Golomb[ Golomb[n] ] ]

int N;
int f[11111111];

int main() {
	ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

	cin >> N;
	f[1] = 1;
	int idx = 1; // 이번에 참조하는 애
	int now = 1; // 이번 index가 채워지는 최대 위치
	while (now < N) {
		idx++;
		f[idx] = 1 + f[idx - f[f[idx - 1]]]; // 공식
		now += f[idx];
	}
	cout << idx << '\n';

	return 0;
}