[Python/BOJ] 6615. 콜라츠 추측

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

6615번: 콜라츠 추측

문제

콜라츠 추측은 흥미로운 현상이다. 이 법칙은 간단해보이지만, 수학적으로 아직까지 증명되어있지 않은 문제이다. 우리는 이 추측이 옳다고 받아들이겠다.

콜라츠 추측을 설명하면 다음과 같다. 우선 다음과 같은 양의 정수 수열 xi 를 생각하자.

• 만약 xi 가 짝수이면, xi+1=xi/2
• 만약 xi 가 홀수이면, xi+1=3*xi +1 이다.

콜라츠 추측은 이렇게 만든 수열은 결국 1이 된다는 것이다.

과학자들은, 컴퓨터를 이용하여 첫 번째 수열이 258 보다 작으면, 이 추측은 참이라고 증명했다.

이제 문제를 보자.

두개의 양의 정수를 준다. 각각의 수에 대해서 콜라츠 추측으로 만든 수열을 생각하자.

각각의 수열을 비교하였을때 처음으로 같은 숫자가 나왔을때 , 각각 몇번째 수열에서 만나는지 구해본다. 문제의 편의를 위해, 이 수열은 1이 나오면 더이상 진행하지 않는다고 하자. ( 1 다음에 나올 수열을 생각하면, 1, 4, 2, 1, 4, 2, 1로 반복되기 때문이다.)

입력

입력은 몇개의 테스트 케이스로 구성된다. 각 테스트 케이스는 두개의 정수 A와 B가 주어진다. ( 1 ≤ A, B ≤ 1,000,000) 마지막 줄은 두개의 0으로 구성된다.

출력

각각의 테스트 케이스마다 다음과 같은 문장을 한줄에 출력한다.

"A needs SA steps, B needs SB steps, they meet at C"

SA와 SB는 A와 B로 수열을 만들고, 처음으로 같은 숫자 C가 나왔을때 각각의 수열에서 몇번째 인지 알려주는 숫자이다.

풀이

Code

import sys
input = sys.stdin.readline

def solution() :
    while True :
        A, B = map(int, input().split())
        if A == 0 and B == 0 : break
        XA, XB = A, B
        # 1. 리스트 생성
        array_A, array_B = [True, A], [False, B]
        # 2. A 정수 배열 생성
        while XA != 1 :
            XA = XA // 2  if XA % 2 == 0 else 3 * XA + 1
            array_A.append(XA)
        # 3. B 정수 배열 생성
        while XB != 1 :
            XB = XB // 2  if XB % 2 == 0 else 3 * XB + 1
            array_B.append(XB)
        # 4. 최초로 맞는 지점 찾기
        target = 0
        for i in range(-1, -min(len(array_A), len(array_B)) - 1, - 1) :
            if array_A[i] != array_B[i] : target = i; break
        # 5. 결과 출력
        print(f'{A} needs {len(array_A) + target} steps, {B} needs {len(array_B) + target} steps, they meet at {array_A[target+1]}')
if __name__ == "__main__":
    solution()