Self-describing Sequence/문보창

No older revisions available

소감 ¶

2006-01-09 Accepted 0.119 3068

Sorted List 이므로 Search 부분에서 Linear Search 대신 Binary Search를 하면 좀 더 효율적이나, 이 정도만 해도 충분히 빠르다. 메모리 사용량을 줄이려면 어떻게 해야 할까?

코드 ¶

~cpp
// 10049 - Self-describingSequence 
#include <iostream>
using namespace std;

#define MAX 673366

static int table[MAX];

void initTable()
{
	int number = 2;
	int count = 0;
	table[1] = 1;
	table[2] = 2;
	table[3] = 2;
	for (int i = 4; i < MAX; i++)
	{
		if (count == 0)
		{
			number++;
			count = table[number];
		}
		count--;
		table[i] = number;		
	}
}

void calcCumulate()
{
	for (int i = 1; i < MAX - 1; i++)
		table[i + 1] += table[i];
}

void preProcess()
{
	initTable();
	calcCumulate();
}

void process(int n)
{
	int i;
	for (i = 1; i < MAX; i++)
		if (n < table[i])
			break;
	if (n == table[i-1])
		i--;
	cout << i << endl;
}

int main()
{
	int n;
	preProcess();
	while (cin >> n && n != 0)
		process(n);
	return 0;
}

----
Self-describingSequence