imported>Unknown at 05:22, 7 February 2021

2021-02-07T05:22:17Z

New page

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

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

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

==== 코드 ====
// 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;
}
==== 덧글 ====

3n 1/이도현 - Revision history

imported>Unknown at 05:22, 7 February 2021