소감 ¶
처음으로 채점로봇에게서 Accepted라는 감격적인 메시지를 안겨준 문제.
정말 수도 없이 많은 시도를 했었다. 하지만 너무나도 꼼꼼하면서도 생각지 못한 테스트 케이스에 항상 좌절했다.
정말 수도 없이 많은 시도를 했었다. 하지만 너무나도 꼼꼼하면서도 생각지 못한 테스트 케이스에 항상 좌절했다.
어려웠던 점 ¶
1. 입력 2개가 범위로 들어가는 데 단순히 첫 번째 입력이 클 것이라는 추측이 잘못되었다. (첫 번째 수가 큰 경우도 있었음)
2. 비트연산자의 위력의 대단함을 느꼈다. 짝홀판별(& 연산자), 나누기2(right shift 1) - 수행속도가 엄청 향상됨.
3. 알고리즘에 대한 명확한 파악이 루프 도는 횟수를 현저히 줄여줌을 배웠다. - 홀수 뒤엔 반드시 짝수가 온다.
4. 첫 번째 당했던 입력의 순서 크기 문제가 출력에서도 다시 말썽 - 단순히 스왑을 시켜버림으로써 원래 입력이 망가지는 모습을 보였다.
2. 비트연산자의 위력의 대단함을 느꼈다. 짝홀판별(& 연산자), 나누기2(right shift 1) - 수행속도가 엄청 향상됨.
3. 알고리즘에 대한 명확한 파악이 루프 도는 횟수를 현저히 줄여줌을 배웠다. - 홀수 뒤엔 반드시 짝수가 온다.
4. 첫 번째 당했던 입력의 순서 크기 문제가 출력에서도 다시 말썽 - 단순히 스왑을 시켜버림으로써 원래 입력이 망가지는 모습을 보였다.
코드 ¶
~cpp
// 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;
}
