백준 14920번: 3n1+1 수열

https://www.acmicpc.net/problem/14920

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을 출력하시오.

2. 알고리즘

키워드 - 구현

 * 접근

점화식에 의해서 입력 받은 수는 언젠가는 1 이 된다.

반복문 내에서 입력 받은 수에 대한 점화식으로 연산을 하고

입력받은 수가 1이 아닐 때까지 카운트를 하면 된다.

3. 코드

#include <iostream>
#include <algorithm> // min
#include <functional>
#include <math.h>
#include <string>
#include <vector>
 
using namespace std;
 
int main()
{
    int n; cin >> n;
 
    vector<int> arr;
 
    int cand = n;
    int count = 1;
    while (cand != 1) {
 
        if (cand % 2 == 0) {
            cand = cand / 2;
            //arr.push_back(cand);
        }
        else {
            cand = cand * 3 + 1;
            //arr.push_back(cand);
        }
        count++;
    }
 
    cout << count << "\n";
    return 0;
}