[Quiz] The 3n + 1 Problem

100_The_3n 1_Problem.pdf

출처 : UVa Online Judge [ http://uva.onlinejudge.org ]


알고리즘 구현 관련 문제에 관심은 있었지만, 지금까지는 제대로 시도한 적이 한 번도 없었는데...
이번에 모~ 회사의 실기 시험을 치르면서 흥미가 생겨서 한 번 풀어봤습니다.
( 사이트에서 작성한 코드에 대한 채점도 가능하더군요~ +_+ )

문제에서 요구하는 입/출력 방식을 감을 못잡아서~ 'Time Limit Exceed' 도 몇 번 보고~~
생각을 살~짝 잘못해서 'Wrong Answer' 도 보고 했지만.. 결국 'Accept' 에 성공했습니다~ : )

문제에 대해 간략한 설명을 하자면...

1. 검사할 범위에 해당하는 두 수(I, J 라고 가정)를 입력 받습니다..

2. I 부터 J 에 속하는 수들 중.. '3n + 1' 연산의 길이가 가장 긴 수를 출력합니다.

3. '3n + 1' 연산의 길이는 수(N)가 홀수인 경우는 3N + 1, 홀수가 아닌 경우는 N / 2 의 연산을 하면서~
    '1' 이 나올 때 까지 연산한 횟수를 말합니다.
     ex) 6 => 6 3 10 5 16 8 4 2 1 [ 길이 : 9 ]
           7 => 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 [ 길이 : 17 ]

4. 출력은 1. 에서 입력받은 두 수와 2. 의 '3n + 1' 연산의 길이가 가장 긴 수를 같이 출력합니다.

   [ 입력값 예시 ]
   1 10
   100 200

   [ 출력값 예시 ]
   1 10 20
   100 200 125

다음은 최종적으로 'Accept' 받은 코드입니다~ : )

 1 //
 2 // 100 - The 3n + 1 Problem
 3 //
 4
 5 #include <iostream>
 6
 7 using namespace std;
 8
 9 int main(void)
10 {
11     int nA, nB, nMin, nMax;
12     int nDepth, nMaxCycleLength, nNumber;
13
14     while (cin >> nA >> nB) {
15         // 입력값에 따른 검사범위 지정
16         if (nA < nB) nMin = nA, nMax = nB;
17         else nMin = nB, nMax = nA;
18
19         nMaxCycleLength = 0;
20
21         for (int i = nMin; i <= nMax; i++) {
22             nNumber = i;
23             nDepth = 1;
24             while (nNumber != 1) {
25                 // [ Type1 ]
26                 // if ((nNumber % 2) == 0) nNumber = nNumber >> 1;
27                 // else nNumber = (3 * nNumber) + 1;
28                 //
29                 // [ Type2 ]
30                 (nNumber % 2) ? nNumber = (3 * nNumber) + 1 : nNumber = nNumber >> 1;
31                 nDepth++;
32             }
33             if (nMaxCycleLength < nDepth) nMaxCycleLength = nDepth;
34         }
35
36         cout << nA << " " << nB << " " << nMaxCycleLength << endl;
37     }
38
39     return 0;
40 }


이번에 모 회사의 실기 시험 문제를 풀면서~ 문제 해결 능력 및 자료구조/알고리즘에 많이 취약하구나 느꼈습니다..;;

앞으로 요런 부분을 꾸준히 보완해 나가야겠다는 반성을 살포시 해봅니다..^^;;