Project Euler #104 (Pandigital Fibonacci ends)

문제는 https://projecteuler.net/problem=104, 언어는 C를 사용했다.

문제를 해석하자면 첫 9자리 숫자와 마지막 9자리 숫자가 pandigital(1~9까지 숫자가 하나씩 반드시 존재)이 되는 피보나치 숫자의 index를 구하는 문제이다.

코드를 요약하자면 각각이 자리수 N개를 저장 가능한 변수를 M개 사용하여 더하기를 구현하여 사용하는 것이다.

아래 코드에서는 long long (typedef로 ubint로 줄여서 사용) 의 범위가 –9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807임을 활용하여 0~(10^18 - 1), 즉 18자리를 이용하고 10^18를 overflow로 간주하여 사용할 것이다.

사실 ubint를 long long 말고 int로 놓고 int최대가능한 10^n을 잡고 풀어도 무방하다.

*여기서 unsigned long long을 사용해도 되지만 그럴 경우 <나 >연산자를 사용할 때 양 변을 unsigned long long으로 항상 맞춰줘야 하므로 벙거로운 일들이 발생한다. 또한 X/10을 해도 X가 10^18이상일 경우 음수 처리가 될 가능성이 있으므로 등등... long long이 편하다.

그리고 add는 어셈블리에서의 add처럼 add(num &a, num &b)가 있을 때 a에 a+b의 결과가 들어가게 하였다.

또한 계산 해야하는 자리수가 커질 경우 a->size 와 b->size를 b->size+1 (왜냐면 이따 보겠지만 a보다 b가 항상 크게 add function안에 들어오게된다.) 로 맞추어 계산범위를 한칸씩 늘려준다.

lastNine은 마지막 9자리 정수를 리턴하고 firstNine은 첫 9자리 정수를 리턴하는데

ubint firstNine(ubint h, ubint l)에서 h != 0일 것으로 간주한다. (그러한 input을 넣지 않으므로)

- 그래서 h의 자리수가 9자리 이상이면 h안에서 firstNine이 나올 것이고

- h의 자리수가 9자리 미만이면 l에서도 일정부분을 h로 올려 return (예를들어 h가 6자리 숫자이면 l에서 첫 3자리를 끌어올려 리턴)

이렇게 동작한다.

ubint firstNine(num *a)는 함수 overloading으로 a에서 h와 l을 골라 firstNine을 돌린다.

이후 while loop가 돌 때마다 index를 기록해주고 (idx에) firstNine과 lastNine을 매번 체크하면서 break해주면 된다.

#include <stdio.h>
#include <windows.h>

#define M 10000
#define N 18

#define NN 1000000000000000000

typedef long long ubint;
struct num {
	ubint n[M]; // –9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807: 18자리 사용 (10^18)
	int size;
};

void init(num &a, ubint base) {
	int i;
	for (i = 0; i < M; i++) a.n[i] = 0;
	a.n[0] = base;
	a.size = 1;
}

bool isPandigital(ubint n) {
	int test[9];
	int i, j;
	bool f;
	for (i = 0; i < 9; i++) {
		test[i] = n % 10;
		n /= 10;
	}
	for (j = 1; j <= 9; j++) {
		f = false;
		for (i = 0; i < 9; i++) {
			if (test[i] == j) {
				f = true;
				break;
			}
		}
		if (!f) return false;
	}
	return true;
}

void add(num &a, num &b) {
	int i;
	for (i = 0; i < b.size; i++) {
		a.n[i] = a.n[i] + b.n[i];
		if (i < M - 1 && a.n[i] >= NN) {
			a.n[i] %= NN;

			a.n[i + 1] += 1;
			if (i + 1 == b.size)
				b.size = a.size = b.size + 1;
		}
	}
}

ubint lastNine(ubint n) {
	return n % 1000000000;
}

ubint firstNine(ubint h, ubint l) {
	ubint th = h;
	int i = 0, j;

	while (th > 0) {
		th /= 10;
		i++;
	}

	if (i > 9) {
		for (j = 0; j < i - 9; j++) h /= 10;
		return h;
	}
	else if (i == 9) return h;
	else if (9 > i && i > 0) {
		for (j = 0; j < 9 - i; j++) {
			h *= 10;
		}
		for (j = 0; j < N - (9 - i); j++) {
			l /= 10;
		}
		return h + l;
	}
	else return -1;
}

ubint firstNine(num *a) {
	if (a->size == 1) return firstNine(a->n[0], 0);
	return firstNine(a->n[a->size - 1], a->n[a->size - 2]);
}

void main() {
	int idx;
	ubint test1, test2;
	num a, b, t;
	init(a, 1);
	init(b, 1);

	idx = 3;
	while (true) {
		add(a, b);
		test1 = lastNine(a.n[0]);
		if (isPandigital(test1)) {
			test2 = firstNine(&a);
			if (test2 != -1 && isPandigital(test2)) {
				break;
			}
		}
		if (idx % 1000 == 0) printf("current? %d\n", idx);

		//printf("%I64d %I64d\n", a.n[0], b.n[0]);
		//system("pause");

		t = b;
		b = a;
		a = t;
		idx++;
	}

	printf("idx = %d\n", idx);
	system("pause");
}