BOJ 6615 - 콜라츠 추측

문제

BOJ 6615 - 콜라츠 추측

콜라츠 수열은 임의의 양의 정수 n에 대해 다음 규칙을 반복해 1에 도달하는 수열이다.

• n이 홀수이면 3n + 1
• n이 짝수이면 n / 2

두 수 A, B가 주어지면 각각의 콜라츠 수열을 생성하고, 두 수열이 처음으로 만나는 지점(공통 조상)과 그 지점까지 각각 필요한 단계 수를 출력한다.

입력

각 줄에 두 양의 정수 A, B가 주어진다. A=0이고 B=0이면 종료한다.

출력

각 테스트 케이스마다 A needs X steps, B needs Y steps, they meet at Z 형식으로 출력한다.

예제

풀이

두 콜라츠 수열의 공통 조상(LCA)을 뒤에서부터 비교하는 역방향 탐색 방법을 사용한다.

1. calc(f, n) 함수로 각 수의 콜라츠 수열을 S[f] 배열에 저장한다. S[f][0]에 수열 길이를 관리하며, 수열 원소를 인덱스 1부터 차례로 저장한다.
2. 두 수열을 뒤(1에 해당하는 끝)에서부터 동시에 비교하며, 같은 값이 이어지는 동안 C에 기록한다.
3. 두 포인터가 달라지거나 한 쪽이 소진되면 비교를 멈춘다. 이때 남은 포인터(S[0][0], S[1][0])가 각각의 남은 단계 수가 된다.
4. A=B인 경우 만나는 지점이 A 자신이므로 별도 처리한다.

핵심 아이디어: 두 수열을 끝(1)에서부터 역방향으로 비교하면, 마지막으로 일치하는 값이 두 수열의 공통 조상이 된다.

코드

#include <iostream>
using namespace std;
using ll = long long;
 
const ll NL = 1e6;
ll A, B, C, S[2][NL + 2];
 
void calc(ll f, ll n)
{
  for (S[f][0] = 1; n != 1;)
  {
    S[f][S[f][0]++] = n;
    if (n & 1)
      n = n * 3 + 1;
    else
      n /= 2;
  }
  S[f][S[f][0]++] = n;
}
 
int main()
{
  cin.tie(0)->sync_with_stdio(0);
  while (cin >> A >> B && A && B)
  {
    calc(0, A), calc(1, B);
    while (S[0][0] > 0 && S[1][0] > 0 && S[0][--S[0][0]] == S[1][--S[1][0]])
      C = S[0][S[0][0]];
    if (A == B)
      C = A;
    cout << A << " needs " << S[0][0] << " steps, " << B << " needs " << S[1][0] << " steps, they meet at " << C << "\n";
  }
}

복잡도

• 시간: O(N log N) — 콜라츠 수열 길이는 n에 대해 O(log n)으로 추정 (미증명이나 실험적으로 확인됨)
• 공간: O(N) — 각 수에 대한 수열 전체를 배열에 저장