[백준] 구현 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×260보다 작은 자연수인 모든 수열은 언젠가는 4, 2, 1로 끝나게 된다는 것이 알려져 있다.

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

입력

C(1); 1 ≤ C(1) ≤ 100000

출력

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

Approach

• 입력받는 수가 n = 1일때이고 반복문을 이용해 그 수가 1이 될때까지 n을 증가시키면 된다. 이때, 수가 짝수일 때는 (이전 수/2), 홀수일 때는 (3 * 이전수 +1) 의 연산을 해줌으로써 수를 업데이트해준다.

Source Code

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    
    int start; // 수 입력받기
    cin >> start;
    
    int n = 1;
    while (start != 1) // 그 수가 1이 될 때까지
    {
        if (start % 2 == 0) // 짝수일 경우 하단의 연산 수행
        {
            start /= 2;
        }
        else // 홀수일 경우 하단의 연산 수행
        {
            start = 3 * start + 1;
        }
        n++; // n 증가
    }
    
    cout << n << endl; // 답안 출력
    
    
    return 0;
}