[백준] 6615번: 콜라츠 추측 (python)

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가 나왔을때 각각의 수열에서 몇번째 인지 알려주는 숫자이다.

 

 

 

 

 

 

풀이)

 

크게 어려운 문제는 아니었는데, 

 

종료조건을 실수로 넣지 않는 바람에 어이없는 곳에서 너무 해매버렸다.

 

import sys
 
while True:
    x, y = map(int, sys.stdin.readline().strip().split())
 
    if x == 0 and y == 0:
        break
 
    temp = x
    a = [-1, x]
    while True:
        if temp == 1:
            break
 
        if temp % 2:
            temp = 3 * temp + 1
            a.append(temp)
        else:
            temp //= 2
            a.append(temp)
 
 
    temp = y
    b = [-2, y]
    while True:
        if temp == 1:
            break
 
        if temp % 2:
            temp = 3 * temp + 1
            b.append(temp)
        else:
            temp //= 2
            b.append(temp)
 
    for i in range(-1, -1000000000, -1):
        if a[i] != b[i]:
            break
 
    # i += 1
    print(f'{x} needs {len(a) + i} steps, {y} needs {len(b) + i} steps, they meet at {a[i + 1]}')

 

---

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

6615번: 콜라츠 추측