BOJ: 14920 3n+1 수열

문제

다음의 점화식에 의해 정해지는 수열 \(C(n)\)을 생각하자.

C(n+1) = C(n)/2     (C(n)이 짝수일 때)
       = 3*C(n)+1   (C(n)이 홀수일 때)

초항 \(C(1)\)이 자연수로 주어지면, 이 점화식은 자연수로 이루어지는 수열을 정한다. 예를 들어, \(C(1) = 26\)이면, 다음의 수열이 된다.

\[26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, ...\]

이 경우, 수열의 뒷부분은 \(4, 2, 1\) 이 끝없이 반복된다. 실제로 \(C(1)\)이 \(5\times2^{60}\)보다 작은 자연수인 모든 수열은 언젠가는 \(4, 2, 1\)로 끝나게 된다는 것이 알려져 있다.

주어진 입력 \(C(1)\)에 대하여 \(C(n)\)이 처음으로 \(1\)이 되는 \(n\)을 출력하시오.

입력

\[C(1); 1 \leq C(1) \leq 100000\]

출력

\(C(n)\)이 처음으로 \(1\)이 되는 \(n\)

예제 입력 1

26

예제 출력 1

11

예제 입력 2

7

예제 출력 2

17

코드

#include <bits/stdc++.h>

using namespace std;

int c(int n, int count) {
    count++;

    if(n == 1)
        return count;

    if(n % 2 == 0)
        return c(n / 2, count);
    else
        return c(3 * n + 1, count);
}

int main(void) {
    int n, count = 0;

    cin>>n;

    cout<<c(n, count);

    return 0;
}

Reference

BOJ