BOJ: 3943 헤일스톤 수열

문제

헤일스톤 수열은 다음과 같이 정의한다.

• \(n\)이 짝수라면, \(2\)로 나눈다.
• \(n\)이 홀수라면, \(3\)을 곱한 뒤 \(1\)을 더한다.

헤일스톤 추측은 임의의 양의 정수 \(n\)으로 수열을 시작한다면, 항상 \(4, 2, 1, 4, 2, 1,...\)로 끝난다는 추측이다. 이 문제에서는 \(1\)이 나오면 수열이 끝난 것으로 처리한다.

\(n\)이 주어졌을 때, 이 수열에서 가장 큰 값을 찾아 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 \(T(1 \leq T \leq 100,000)\)가 주어진다. 다음 줄부터 \(T\)개의 줄에는 헤일스톤 수열의 시작값 \(n\)이 주어진다. \((1 \leq n \leq 100,000)\)

출력

각각의 테스트 케이스에 대해서, \(n\)으로 시작하는 헤일스톤 수열에서 가장 큰 값을 출력한다.

예제 입력 1

4
1
3
9999
100000

예제 출력 1

1
16
101248
100000

코드

#include <bits/stdc++.h>

using namespace std;

int c(int n, int max) {

    if(max < n)
        max = n;

    if(n == 1)
        return max;

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

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int n, t;
    int max;

    cin>>t;

    for(int i=0; i<t; i++) {
        cin>>n;

        max = n;

        cout<<c(n, max)<<'\n';
    }

    return 0;
}

Reference

BOJ