[BOJ 6615 // C++] 콜라츠 추측

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 6615번 문제인 콜라츠 추측이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/6615

6615번: 콜라츠 추측

이 문제에서는 두 숫자 A, B로 Collatz sequence를 만들 때 몇 번째 숫자에서 처음으로 만나는지를 구해야 한다.

두 숫자가 처음으로 같아지는 순간이 오면, 그 이후로 서로 다른 숫자가 나올 수 없으므로

두 Collatz 수열의 뒤부터 앞으로 서로 다른 수가 나올 때까지 한칸씩 이동하여 문제를 풀 수 있다.

 

주어지는 입력은 100만 이하이지만 수열의 값은 int범위를 넘어설 수 있다는 점에 유의하자.

또한, 위키백과에 따르면, 100만 미만 수로 시작하는 Collatz sequence의 길이의 최댓값은 524이다.

(837799로 시작하는 수열이다.) 따라서 배열의 크기를 지나치게 크게 선언할 필요는 없다.

 

모든 Collatz sequence는 1로 끝난다는 문제의 가정을 받아들이면(실제로 100만 이하의 범위에서는 성립), 두 Collatz sequence는 모두 1로 끝나므로 이 알고리즘은 잘 작동한다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;

long long arrA[530]; // 1000000 미만에서 나올 수 있는 길이의 최댓값은 524 
long long arrB[530];

int main()
{
    cin.tie(0);

    long long A, B; // A와 B는 int범위를 벗어날 수 있음에 유의
    cin >> A >> B;
    while (A != 0 and B != 0) { //종료 조건
        int originalA = A;
        int originalB = B;
        int pA = 0, pB = 0;
        while (A != 1) { // Collatz sequence of A
            arrA[pA] = A;
            if (A % 2 == 1) A = 3 * A + 1;
            else A = A / 2;
            pA++;
        }
        arrA[pA] = 1;
        while (B != 1) { // Collatz sequence of B
            arrB[pB] = B;
            if (B % 2 == 1) B = 3 * B + 1;
            else B = B / 2;
            pB++;
        }
        arrB[pB] = 1;
        while (arrA[pA] == arrB[pB]) { // 서로 다른 수가 나올 때까지 1부터 거꾸로 탐색
            pA--;
            pB--;
            if (pA == -1 or pB == -1) break;
        }
        int sA = pA + 1;
        int sB = pB + 1;
        long long C = arrA[sA];
        printf("%i needs %i steps, %i needs %i steps, they meet at %lld\n", originalA, sA, originalB, sB, C);
        cin >> A >> B;
    }
}