프로젝트 오일러 51
projecteuler, cpp느린 풀이
가장 작은 수를 구해야 하므로 알고리즘의 방향은 작은 수에서 큰 수로 진행할 것이다. 또 치환할 자리수를 뽑는 것은 조합이므로, 조합 코드를 만들어야 한다. 그리고 수에 대한 digit을 다뤄야 하므로, 이를 다루는 함수를 많이 만들었던 오일러 49번 문제의 코드를 갖다 쓰자.
이렇게 풀이를 계획하고 첫 코드를 짜서 돌려 보니 96.726 초가 걸린다. 답은 나왔지만, 코드가 꼬인 느낌도 들고 실행시간도 길다. 더 좋은 방법이 없을까?
/*
Problem 51 - Prime digit replacements
*/
#include <iostream>
#include <ctime>
#include <map>
#include <cmath>
#include <vector>
#include <math.h>
#include <string.h>
using namespace std;
std::map<int,int> primes;
bool isprime( int n)
{
if( n == 2) return true;
std::map<int,int>::iterator it = primes.find(n);
if( it != primes.end()) { return true; }
int s = sqrt( n) + 1;
for(int i=s; i>1; i--)
{
if (n%i ==0) { return false; }
}
primes.insert( std::map<int,int>::value_type( n, n));
return true;
}
int toint( int n[], int size)
{
int toi = 0;
for(int i=0; i<size; i++)
{
toi += pow(10, i) * n[i];
}
return toi;
}
void inc( int n[], int size)
{
n[0]++;
for(int i=0; i<size; i++)
{
if(n[i] >= 10) {
if(i+1 < size) {
n[i+1] += n[i]/10;
}
n[i] = n[i]%10;
} else {
break;
}
}
}
#define MAX 8
int n[MAX] = {0,};
void combination( int arr[], int arrsize, int choose, int nowi, std::vector<int> result, bool* done)
{
if( choose <= 0) {
vector<int> replacedNumbers;
for(int i=0;i<10;i++)
{
int r[MAX];
memcpy( r, n,sizeof(int)*MAX);
bool nopush = false;
for( std::vector<int>::iterator it= result.begin(); it!=result.end();++it)
{
if( i == 0 && *it == arrsize-1) {
nopush = true;
break;
}
r[*it] = i;
}
if (!nopush){
replacedNumbers.push_back(toint(r, MAX));
}
}
int nPrimes = 0;
for(int i=0; i<replacedNumbers.size(); i++)
{
if (isprime( replacedNumbers[i])) {
nPrimes++;
}
}
if( nPrimes == 8) {
cout << "\tfound!" << endl;
for(int i=0; i<replacedNumbers.size(); i++)
{
if( isprime( replacedNumbers[i])) {
cout << replacedNumbers[i] << " ";
}
}
cout << endl;
*done = true;
}
return;
}
for(int i=nowi; i<arrsize;i++)
{
std::vector<int> r(result);
r.push_back(i);
combination( arr, arrsize, choose-1, i+1,r, done);
}
}
int main(int argc, char** argv)
{
clock_t begin = clock();
/* starting code */
n[1] = 1; // starting at 10
int digits = 1;
bool done = false;
while( !done)
{
int ntoi = toint( n, MAX);
int d = int(log10(ntoi)+1);
if( d> digits) digits = d;
for(int i=1;i<=digits; i++)
{
int digitlist[MAX] = {0,};
for(int j=0;j<digits-1; j++)
{
digitlist[j] = j;
}
std::vector<int> c;
combination( digitlist, digits, i, 0, c, &done);
}
cout << "n=" << ntoi << endl;
inc( n, MAX);
}
/* end of code */
clock_t end = clock();
std::cout << "elapsed time=" << double(end - begin) / CLOCKS_PER_SEC << std::endl;
return 0;
}