BOJ 3943 - 헤일스톤 수열

문제

양의 정수 N에서 시작하여 홀수면 3N+1, 짝수면 N/2를 반복할 때, 1에 도달하기까지 나타나는 수열의 최댓값을 구하라.

입력

첫째 줄에 테스트 케이스 수 T, 이후 T줄에 N이 주어진다.

출력

각 N에 대해 수열의 최댓값을 출력한다.

예제

입력	출력
`1` `3`	`16`

풀이

콜라츠 추측(헤일스톤 수열)을 시뮬레이션하며 최댓값을 추적한다.

N이 1보다 클 동안 반복한다
홀수면 3*N + 1, 짝수면 N / 2로 갱신한다
매 단계에서 현재 값과 최댓값을 비교하여 갱신한다
값이 커질 수 있으므로 unsigned long long을 사용한다

핵심 아이디어: 비트 AND 연산(n & 1)으로 홀짝을 O(1)에 판별하며, 수열이 반드시 1에 수렴한다는 가정(콜라츠 추측) 하에 시뮬레이션한다.

코드

#include <bits/stdc++.h>
using namespace std;
 
#define ullint unsigned long long int
 
int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int T;
  cin >> T;
  while (T--)
  {
    ullint n;
    cin >> n;
    ullint tck_max = n;
    while (n > 1)
    {
      n = n & 1 ? n * 3 + 1 : n / 2;
      tck_max = max(tck_max, n);
    }
    cout << tck_max;
    if (T)
    {
      cout << '\n';
    }
  }
  return 0;
}

복잡도

시간: O(T * K) (K는 수열이 1에 도달할 때까지의 반복 횟수)
공간: O(1)

문제