문제보기

  이번 문제도 한 번에 AC를 받지는 못했다. 3n+1 문제에 이어 또 한번의 좌절을 겪고 있을 때 의외로 간단히 해결책을 알아냈다. 단지 배열의 크기를 조금 더 크게 하는 것으로 문제를 해결했다. 결국 Online Judge가 너무 엄격하다고 밖에 생각이 안 된다.

소스

#include "iostream"
#include "stdio.h"
#define MAX 101

using namespace std;

int main()
{
	int i, j; // 지뢰밭의 크기(i, j)
	int m, n; // *를 중심으로 주변부 8개의 값을 1씩 더하기 위해 사용(m, n)
	int l, c; // 지뢰밭 배열을 초기화 하고 입출력을 위한 변수
	int fieldnum=1; // 필드번호
	char line[MAX]; // 지뢰밭을 입력받을 때 사용하는 배열
	char field[MAX][MAX]; // 지뢰밭 배열


	while(i || j)
	{
		// 두 정수를 입력받는다.
		cin >> i >> j;
		if(i==0 || j==0 || i >100 || j>100)
			break;

		// field 배열을 초기화
		for(l=0; l<i; l++)
		{
			for(c=0; c<j; c++)
			{
				field[l][c]='0';
			}
		}

		// 한 줄씩 입력받고, 입력 받을 때마다 값을 읽고 field 배열에 반영
		for(l=0; l<i; l++)
		{
			cin >> line;
			for(c=0; c<j; c++)
			{
				if(line[c] == '*')
				{
					field[l][c] = '*'; // mine을 필드에 표시
					// 주위 8개의 값을 1씩 더함
					for(m=0; m<3; m++)
					{
						for(n=0; n<3; n++)
						{
							if(field[l-1+m][c-1+n]!='*') // 필드의 값이 '*'이 아닐 경우에만 1을 더함
							field[l-1+m][c-1+n] += 1;
						}
					}

				}
			}
		}
		
		// 출력
		if (fieldnum >1 ) cout << endl;
		cout << "Field #" << fieldnum << ":" << endl;
		for(l=0; l<i; l++)
		{
			for(c=0; c<j; c++)
			{
				cout << field[l][c];
			}
			cout << endl;
		}
		fieldnum++;
	} // end of while
	return 0;
}

소스에서 #define MAX 100으로 처음 했더니 WA를 받았다. 정확한 이유는 글쎄-_-;(아래 글상자 참고) 구글에서 검색하다가 이 페이지에서 다음과 같은 내용을 발견하고 소스를 수정했다.

Increase your array (out) size to 101.

On a 100x100 board, you sometimes attempt to increase out[x][100], which in memory is the same as out[x+1][0] and is thus incrementing something you don't want to.

Also, you can make the array size 102 and start everything at 1, so you don't have to worry about indexes going below 0 as well, and eliminate the bounds checking altogether.

Alternatively, you can just fix your bounds checking, but the above recommendation is probably quicker.

한 가지 의외였던 것은 배열에서 '*'를 검사한 후 주변부 8개의 값을 1씩 더해줄 때 경계에 있는지 확인하지 않아도 프로그램이 잘 돌아간다는 것이다. 배열 인덱스가 음수가 되면 에러가 날 줄 알았는데 컴파일러에서 알아서 처리하는 모양이다.

이제 겨우 두 문제를 풀어보았는데 아직 UVa 문제가 익숙하지 않아서인지 때로는 문제의 조건이 부족하다는 생각이 든다. 예를 들어 이 문제의 경우 n과 m값 중에서 둘 중에 하나만 0이 입력될 경우에는 어떻게 할 것인지, 혹은 100 이상이 될 경우에는 어떻게 할 것인지에 대한 조건이 없다. 문제에 0 < n, m <= 100 란 조건이 있는데 입력되는 값은 이 범위를 벗어나지 않는다는 가정을 했다고 생각하는 수 밖에 없는 듯.

C문법만 알고 C++문법은 거의 잘 몰라서 소스를 작성하는 것도 고민이 된다. C++에 관한 책을 좀 찾아봐야 할 것 같다.

  어제 광화문 교보문고에서 알고리즘 트레이닝 북(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를 받고 시작하고 싶었지만 의미없는 것에 시간을 너무 쏟고 있는 것 같아 다음에 기회가 되면 해결하기로 하고 다음 문제로 넘어가려 한다. 사실 찝찝함을 도저히 감출수가 없다-_-;