세제곱수의 순열(permutation)

 

오랜만에 머리도 식힐(?) 겸 프로젝트 오일러를 하나 풀어봤다.

문제의 골자는 세제곱수 중에 순열을 이루는 것이 다섯 개 있는 것을 찾아내는 것.

 

이 문제는 사실 unsigned long long을 사용하면 그닥 어렵지 않게 만들 수 있다.

 

몇 가지 포인트만 잡으면 꽤 빠르게 동작하는 프로그램을 만들 수 있다.

 

1. 모든 자릿수의 모든 숫자를 대상으로 계산하면 너무 복잡해짐

2. 세제곱수의 자릿수를 결정한 뒤 그 범위에 해당되는 세제곱근들만 계산

 

#include <cstdio>
#include <vector>
#include <cmath>

using namespace std;

bool ArePermutated(unsigned long long b1, unsigned long long b2) {
	int cnt[10];
	memset(cnt, 0, sizeof(cnt));

	while (b1) {
		++cnt[b1 % 10];
		b1 /= 10;
	}

	while (b2) {
		--cnt[b2 % 10];
		b2 /= 10;
	}

	for (int i = 0; i < 10; ++i) {
		if (cnt[i]) { return false; }
	}

	return true;
}

int main()
{
	unsigned digits = 8;
	bool solutionfound = false;
	while (!solutionfound) {
		unsigned low = (unsigned)pow(10.0, (digits - 1) / 3.0);
		unsigned high = (unsigned)pow(10.0, digits / 3.0);

		vector<unsigned long long> bigints;

		for (unsigned i = low; i <= high; ++i) {
			bigints.push_back((unsigned long long)i * i * i);
		}

		vector<unsigned> result;
		for (unsigned i = low; i < high; ++i) {
			result.clear();
			result.push_back(i);
			for (unsigned j = i + 1; j <= high; ++j) {
				if (ArePermutated(bigints[i - low], bigints[j - low])) {
					result.push_back(j);
				}
			}

			if (result.size() == 5) {
				printf("result: %u, %u, %u, %u, %u\n", result[0], result[1], result[2], result[3], result[4]);
				solutionfound = true;

				printf("%u ^ 3 = %llu\n", result[0], (unsigned long long)i * i * i);

				break;
			}
		}

		++digits;
	}

	return 0;
}

 

그런데, 막상 해놓고 보니 조금은 더 빠르게 할 수 있는 방법들이 눈에 띈다.

더불어, 조건이 좀 더 복잡해져 훨씬 긴 자릿수가 요구되면 대응할 수 없다는 한계도 보이고.

 

방법은 간단(?)하다.

vector<char>로 별도의 BigInt 형을 구현하는 것.

순열 여부 판단도 이 쪽이 좀 더 빠르게 구현 가능하다.

 

#include <cstdio>
#include <vector>
#include <cmath>

using namespace std;

//vector<char> 형으로 big int 구현
//단, 0은 빈 vector로 표현
typedef vector<char> BigInt;

void BigLetPositive(BigInt& big, unsigned num) {
	big.clear();
	
	while (num) {
		big.insert(big.begin(), (char)(num % 10));
		num /= 10;
	}
}

void BigPrintf(BigInt& big) {
	if (big.empty()) {
		printf("0");
	}
	else {
		for (size_t i = 0; i < big.size(); ++i) {
			printf("%d", big[i]);
		}
	}
}

void BigMultiply(BigInt& result, BigInt& a, BigInt& b) {
	result.clear();
	if (a.empty() || b.empty()) { return; }

	size_t sa = a.size();
	size_t sb = b.size();
	size_t sr = sa + sb;
	result.resize(sr, 0);

	for (size_t i = 0; i < sa; ++i) {
		for (size_t j = 0; j < sb; ++j) {
			result[i + j + 1] += a[i] * b[j];
		}

		for (size_t j = sr - 1; j > 0; --j) {
			if (result[j] > 9) {
				result[j - 1] += (result[j] / 10);
				result[j] %= 10;
			}
		}
	}

	if (!result[0]) {
		result.erase(result.begin());
	}
}

bool BigArePermutated(BigInt& b1, BigInt& b2) {
	if (b1.size() != b2.size()) { return false; }
	int cnt[10];
	memset(cnt, 0, sizeof(cnt));

	size_t s = b1.size();
	for (size_t i = 0; i < s; ++i) {
		++cnt[b1[i]];
		--cnt[b2[i]];
	}

	for (int i = 0; i < 10; ++i) {
		if (cnt[i]) { return false; }
	}

	return true;
}

void BigGetCube(BigInt& cube, unsigned num) {
	BigInt big;
	BigLetPositive(big, num);
	
	BigInt big2;
	BigMultiply(big2, big, big);

	BigMultiply(cube, big2, big);
}

int main()
{
	DWORD dw = GetTickCount();

	unsigned digits = 8;
	bool solutionfound = false;
	while (!solutionfound) {
		unsigned low = (unsigned)pow(10.0, (digits - 1) / 3.0);
		unsigned high = (unsigned)pow(10.0, digits / 3.0);

		vector<BigInt> bigints;

		for (unsigned i = low; i <= high; ++i) {
			BigInt t;
			BigGetCube(t, i);
			bigints.push_back(t);
		}

		vector<unsigned> result;
		for (unsigned i = low; i < high; ++i) {
			result.clear();
			result.push_back(i);
			for (unsigned j = i + 1; j <= high; ++j) {
				if (BigArePermutated(bigints[i - low], bigints[j - low])) {
					result.push_back(j);
				}
			}

			if (result.size() == 5) {
				printf("result: %u, %u, %u, %u, %u\n", result[0], result[1], result[2], result[3], result[4]);
				solutionfound = true;

				printf("%u ^ 3 = ", result[0]);
				BigInt t;
				BigGetCube(t, i);
				BigPrintf(t);
				printf("\n");

				break;
			}
		}

		++digits;
	}

	return 0;
}

 

이 코드를 돌려보면 위의 unsigned long long을 사용한 코드보다 10배 가까이 더 빠르게 동작하는 것을 볼 수 있다.

 

 

덧, unsigned long long 쪽은 64비트로 컴파일하면 32비트에 비해 세 배 이상 빠르게 동작한다. ㄷㄷㄷ