어제 광화문 교보문고에서 알고리즘 트레이닝 북(Programming Challenges)을 구입하였다. UVa에 게제되어 있는 수많은 문제들 중에서 핵심 알고리즘을 학습하는 데 필요한 문제들을 엄선해 놓은 책이다. 그 중 첫번째 문제는 3n+1문제인데 Online Judge가 엄격해서인지 계속 WA(Wrong Answer)가 뜬다. 벌써 어제부터 하루종일 이 문제만 붙잡고 있었는데 첫 문제부터 이렇게 사람속을 썩이니 학습에 대한 의욕을 반감시키는 것 같다.

  처음 이 문제에 대한 해답을 제출했을 때의 응답은 시간제한초과(Time limit exceeded)였다. 문제가 무엇인가 찾아 보았더니 n의 값이 113383일 때 32bit의 정수 범위를 초과하면서 무한루프(infinite loop)에 빠졌기 때문이다. 그래서 문제의 조건인 n이 0이하이거나 1,000,000 이상일 경우에는 사이클 길이(Cycle length)를 구하지 않도록 했다. VC++에서 컴파일 했을 때는 완벽하게 작동하였고 실행속도에도 이상이 없었다. 하지만 이 상태로 UVa에 제출하면 역시 WA라는 대답만 돌아온다.

  인터넷을 돌아다니다가 C++로 작성된 답을 찾게 되었다. UVa에 제출하여 보니 AC(Accepted)가 뜬다. 그런데 이해가 안 되는 부분은 이 코드를 실행해보면 무한루프에 빠진다는 것이다. 그런데 어째서 UVa에서는 AC까 뜨는지 모르겠다.

인터넷에서 구한 C++코드

/*	@JUDGE_ID:	110101	100	C++	*/

/* @BEGIN_OF_SOURCE_CODE */

#include "iostream"

using namespace std;

int main()
{
	int oriStart = 0;
	int oriEnd = 0;

	while(cin >> oriEnd >> oriStart != 0) ///< 두개의 값을 입력받는다.
	{
		int start = oriStart;
		int end = oriEnd;

		int maxCount = 0; ///< 최대 사이클 횟수를 저장

		if(end > start) ///< 만약 서로 입력 순서가 바뀌었다면 서로 바꿔준다.
			swap(end, start);

		for(int i = end; i <= start; ++i)
		{	
			if(i < 1 || i >= 1000000) ///< 예외처리 코드
				continue;

			int count = 1;		
			int result = i;

			while(result != 1)
			{
				if(!(result & 1)) ///< 짝수일때  == if(result % 2 == 0)
				{
					result >>= 1;; ///< == result /= 2
				}
				else ///< 홀수일때
				{
					result = result * 3 + 1;
				}
				++count;
			}
			if(count > maxCount) ///< 현재 수가 최대 사이클을 기록했다면 기록을 갈아치우자
				maxCount = count;
		}
		cout << oriEnd << " " << oriStart << " " << maxCount << endl;
	}

	return 0;
}

/* END_OF_SOURCE_CODE */

내가 작성한 코드

/* @BEGIN_OF_SOURCE_CODE */

#include "stdio.h"
const long MAXINT=1000000;


int main()
{
	int i, j, k, n;
	int begin, end;
	int count, maxcount;

	while(scanf("%ld %ld", &i, &j)==2)
	{
		begin = i;
		end = j;
		maxcount = 0;

		if(begin>end) 
		{
			k=begin;
			begin=end;
			end=k;
		}

		while(begin<=end)
		{
			if(begin < 1 || begin >= MAXINT)
			{
				begin++;
				continue;
			}
			n = begin;
			count=1;

			while(n!=1)
			{
				if(n > MAXINT)
				{
					count=0;
					break;
				}
				if(n&1) // 홀수일 때
				{
					n = 3*n+1;
				}
				else // 짝수일 때
					n=n/2;
				count++;
			}
			if(maxcount < count)
				maxcount = count;
			begin++;
		}
	printf("%d %d %d\n", i, j, maxcount); 
	}
	

	return 0;
}

/* END_OF_SOURCE_CODE */

  첫번째 문제라서 반드시 AC를 받고 시작하고 싶었지만 의미없는 것에 시간을 너무 쏟고 있는 것 같아 다음에 기회가 되면 해결하기로 하고 다음 문제로 넘어가려 한다. 사실 찝찝함을 도저히 감출수가 없다-_-;