[3943번] 헤일스톤 수열

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 구현

다이나믹 프로그래밍이라기 보단 그냥 구현에 가까운 것 같다.

이 문제의 정말 치명적인 함정은, cout을 적는다면 TLE이다.(cin은 더할나위 없다.)

하라는 대로 해준다.

n이 짝수라면 2로 나누고, n이 홀수라면 3을 곱하고 1을 더해준다.

이 과정에서 행여나 int범위를 넘어설 수 있으니, long long으로 안전하게 처리해준다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
typedef long long ll;
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while (tc--)
    {
        ll n;
        scanf("%lld", &n);
 
        ll get = 1;
        while (n != 1)
        {
            get = max(get, n);
            if (n % 2 == 0)
                n /= 2;
            else
                n = n * 3 + 1;
        }
 
        printf("%lld\n", get);
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>