문제

콜라츠의 추측, 3n+1 문제, 우박수 문제라고 불리는 이 문제는 다음과 같다.

1, 어떤 자연수 n이 입력되면,

2. n이 홀수이면 3n+1을 하고,

3. n이 짝수이면 n/2를 한다.

4. 이 n이 1이 될때까지 2~3과정을 반복한다.

예를 들어 5는 5 → 16 → 8 → 4 → 2 → 1 이 된다.

여기서 5가 1이되기 위해 6개의 숫자를 나열하게 된다. 이것을 길이라고 하면 5의 길이는 6이된다.

시작수와 마지막 수가 입력되면 그 두 사이게 길이가 가장긴 우박수와 그 길이를 출력하시오.

입력

두 자연수 a, b가 공백으로 분리되어 입력된다. ( 1 <= a <= b <= 10,000 )

입력 예시

1 10

출력

a에서 b사이에 길이가 가장긴 우박수와 그 길이를 출력한다. 만약 가장 긴 수가 두 개이상인 경우, 작은 숫자를 출력하시오.

출력 예시

9 20

문제 풀이

여태까지 푼 문제 중에서 가장 많은 시간을 투자한 것 같다.
일단 해당 문제를 풀기 전에, 우박수 로직에 대한 부분을 어떤식으로 구현할지 생각했다.

1. 우리가 구해야하는 값이 무엇인지?
2. 해당 값을 구하기 위해서는 값을 어떤 식으로 저장해야 하는지?
3. 주어진 범위 내의 모든 수의 우박수와 우박수 길이에서 우박수 길이가 가장 긴 데이터만 어떻게 출력 시킬건지?

처음에는 재귀함수를 통해 불러오려고 했으나, 그게 마음대로 되지가 않아서 재귀함수로 불러오는 방식을 포기하고 다시 소스코드를 작성하였다.

어떤 식으로 값을 저장할지 상당히 많은 시간 고민을 했는데, 아무래도 우박수와 해당 우박수의 길이를 저장해야하기 때문에, dictionary형을 선택하였다.

값을 정상적으로 저장만 할 수 있다면, dicitionary에서 max value를 구하는 것은 어렵지 않았다.

약 2시간을 고민하고 삽질해서 풀었다.. 진짜 머리 빠개지는줄 알았다.
문제를 풀고 다른사람들의 코드를 보니 메모제이션을 이용하여 시간을 줄이는 사람도 있었는데 이 부분은 시간이 있을때 해당 방법도 적용하여 풀어볼 예정이다.
(지금은 힘들어서 이제 그만~)

min_range, max_range = map(int,input().split(" "))

def odd(num):
    result = (num * 3) + 1
    return int(result)

def even(num):
    result = num/2
    return int(result)

collatz_num = {}

for i in range(min_range, max_range+1):
    number, length = i,1
    while number != 1:
        if number % 2 == 0:
            number = even(number)
            length += 1
        else:
            number = odd(number)
            length += 1
    collatz_num[i] = length

max_key = max(collatz_num, key=collatz_num.get)
print(f"{max_key} {collatz_num[max_key]}")