프로젝트 오일러 44

합과 차도 모두 오각수인 두 오각수 차의 최소값은?

이 문제에서 가장 고민이 되는 건 $j$ 와 $k$ 를 어찌 찾아가야 하냐는 것인데, 다음 두 가지를 고려해서 알고리즘을 돌릴 방향을 정했다.

1) 오각수 $P_n$ 과 다음 오각수 $P_{n+1}$ 간의 간격은 점점 멀어진다. 즉 오각수의 증가폭은 점점 커진다.

2) 문제에서는 조건을 만족하는 어떤 두 오각수의 차이가 가장 작을 때를 구해야 한다.

알고리즘에서는 $P_n$ 을 구한 다음, 차이가 오각수인지 $P_{n-1}$ , $P_{n-2}$ , … 방향으로 먼저 따져본다. 차이가 오각수였다면 합이 오각수인지도 따져본다. 답을 못 구했으면 $P_{n+1}$ 에 대해서 이 과정을 반복한다.

이렇게 풀면 자기보다 작은 오각수에 대해서는 답이 없을 것이 보장된다. 1.04 초 정도의 실행시간으로 문제가 풀리긴 했으나, 생각해보니 빠진 경우의 수도 있다. 자기보다 큰 오각수지만 간격값이 작은 경우에서 답이 나올 가능성이 있다. 즉 오각수 간격이 내가 구한 답의 크기를 넘어갈 때까지 큰 오각수들을 검사해봤어야 완벽한 커버가 될 것 같다. 풀고 나니 허점이 보이지만, 딱히 코드에 반영은 안함. ^^;;

/*
 	Problem 44 - Pentagon numbers 
*/
#include <iostream>
#include <ctime>
#include <map>

std::map<int,int> pentagonals;

using namespace std;

int main(int argc, char** argv)
{
	clock_t begin = clock();
	/* starting code */
	std::map<int,int>::iterator it;
	std::map<int,int>::iterator exist;
	int nextn = 1;

	while( true) {
		int newp = nextn*(3*nextn-1)/2;

		for( it = pentagonals.end(); it != pentagonals.begin(); --it)
		{
			int diff = newp - it->first;
			exist = pentagonals.find( diff);
			if( exist != pentagonals.end()) {

				int sum = newp + it->first;

				for( int i=nextn+1;;i++)
				{
					int tri = i*(3*i-1)/2;
					exist = pentagonals.find(tri);
					if ( exist == pentagonals.end()) {
						pentagonals.insert( std::map<int,int>::value_type( tri, tri));
					}

					if( sum == tri) {
						cout << "found! newp=" << newp << " with " << it->first << ", so diff=" << newp-it->first << endl;
						goto done;
					}
					if (tri > sum) { break;}
				}

			}
		}
	
		exist = pentagonals.find(newp);
		if ( exist == pentagonals.end()) {
			pentagonals.insert( std::map<int,int>::value_type( newp, newp));
		}
		nextn++;
	}

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