어떤 수에 (1, 2, ... )를 곱해서 이어붙여 얻을 수 있는 가장 큰 1 ~ 9 팬디지털 수

[eng][kor]

알고리즘을 돌릴 상한(=n을 곱해갈 the number의 최대값)만 찾으면, 이전에 풀었던 문제와 크게 다르지 않다.

the number 의 최대값은 어떻게 구해야 할까? 문제에서 n이 1보다 무조건 커야 한다고 했으므로, pandigital 여부를 따져볼 때 the number * 1 과 the number * 2 까지는 구해서 이어붙어야 한다. 즉.. the number * 1 과 the number * 2 두개의 수를 이어붙였을 때, pandigital인 9자리 수보다 작거나 같아야 한다. 따라서 the number 의 최대값은 네자리 수 9999 이다.

/*
  Problem 38 - Pandigital multiples
*/

#include <iostream>
#include <ctime>

using namespace std;


bool isPandigital( char arr[])
{
	if (strlen(arr) != 10) { return false; }

	bool swit[10] = {false,};
	for(int i=0; i<10; i++)
	{
		int idx = arr[i] - '0';
		if (swit[idx] == true) { return false; }
		else { swit[idx] = true; }
	}

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

void multiplesAttach( char buf[], int n)
{
	buf[0] = '0';
	char* c = &buf[1];
	for(int i=1;; i++)
	{
		int mul = n*i;
		c += sprintf( c, "%d", mul);
		int len = strlen( buf);
		if (len >= 10) { return; }
	}
}

int main(int argc, char** argv)
{
  clock_t begin = clock();
 
	/* starting code */

	// 10000 * 1 = 10000, 10000 * 2 = 20000 (1000020000 : 10개. Pandigital 자리수 초과!)
	for(int i=1; i<9999; i++)
	{
		char s[32] = {0,};
		multiplesAttach( s, i);
		if (isPandigital( s)) {
			cout << "pandigital at i=" << i << " s=" << s << endl;
		}
	}

  /* end of code */
  clock_t end = clock();
  std::cout << "elapsed time=" << double(end - begin) / CLOCKS_PER_SEC << std::endl;
  return 0;
}