3n 1/이도현

문제

2005-12-30 14:39:20 Accepted 3.256 436 56031 C++ 100 - The 3n + 1 problem

소감

처음으로 채점로봇에게서 Accepted라는 감격적인 메시지를 안겨준 문제. 정말 수도 없이 많은 시도를 했었다. 하지만 너무나도 꼼꼼하면서도 생각지 못한 테스트 케이스에 항상 좌절했다.

어려웠던 점

1. 입력 2개가 범위로 들어가는 데 단순히 첫 번째 입력이 클 것이라는 추측이 잘못되었다. (첫 번째 수가 큰 경우도 있었음)
2. 비트연산자의 위력의 대단함을 느꼈다. 짝홀판별(& 연산자), 나누기2(right shift 1) - 수행속도가 엄청 향상됨.
3. 알고리즘에 대한 명확한 파악이 루프 도는 횟수를 현저히 줄여줌을 배웠다. - 홀수 뒤엔 반드시 짝수가 온다.
4. 첫 번째 당했던 입력의 순서 크기 문제가 출력에서도 다시 말썽 - 단순히 스왑을 시켜버림으로써 원래 입력이 망가지는 모습을 보였다.

코드

// The 3n + 1 problem
// UVa ID : 100
#include <iostream>
using namespace std;
int cycle_length(int input);

int main()
{
	int input1, input2;

	while (cin >> input1 >> input2)
	{
		int i;
		int max_count = -1;
		int temp = 0;
		
		// 입력의 순서가 절대 뒤바뀌면 안된다!!
		cout << input1 << " " << input2 << " ";

		// 앞에 들어오는 입력이 뒤에 입력보다 더 클 경우 (for문 에러 방지)
		if (input1 > input2)
		{
			int swap = input1;
			input1 = input2;
			input2 = swap;
		}

		for (i = input1; i <= input2; i++)
		{
			temp = cycle_length(i);				// cycle legnth 찾기
			if (temp > max_count)
				max_count = temp;				// 큰 수를 max_count로
		}
		cout << max_count << endl;
	}

	return 0;
}

// cycle length 구하기
int cycle_length(int input)
{
	int argument = input;		// 전달인자로 넘어온 수 저장
	int count = 0;				// 카운트 변수
	
	while (true)
	{
		// 종료 조건
		if (argument == 1)
		{
			count++;
			break;
		}

		// LSB가 0이면 짝수, 1이면 홀수이다.
		if ((argument & 1) == 0)
		{
			// 나누기 2는 right shift를 한 번 하는 것과 같다.
			argument >>= 1;
			count++;
		}
		else
		{
			// 홀수라면 반드시 다음은 짝수가 온다.
			argument = 3 * argument + 1;
			argument >>= 1;
			count += 2;
		}
	}

	return count;
}