[Python] 코딩 도장 - 3n+1 Problem

코딩 도장 사이트의 문제를 직접 풀어본 내용을 정리하여 올립니다.

코딩 도장에서 여러 문제를 확인할 수 있습니다.

난이도 순으로 차근차근 풀어보려 합니다.

---

[문제: 3n+1 Problem] - Lv.2

어떤 정수 n에서 시작해, n이 짝수면 2로 나누고, 홀수면 3을 곱한 다음 1을 더한다.

이렇게 해서 새로 만들어진 숫자를 n으로 놓고, n=1 이 될때까지 같은 작업을 계속 반복한다.

예를 들어, n=22이면 다음과 같은 수열이 만들어진다.

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

n이라는 값이 입력되었을때 1이 나올때까지 만들어진 수의 개수(1을 포함)를 n의 사이클 길이라고 한다.

위에 있는 수열을 예로 들면 22의 사이클 길이는 16이다.

i와 j라는 두개의 수가 주어졌을때, i와 j사이의 모든 수(i, j포함)에 대해 최대 사이클 길이를 구하라.

입력 예

1    10
100  200
201  210
900  1000

출력 예

1    10    20
100  200   125
201  210   89
900  1000  174

참고

어떤 자연수 n에 대해서도, 이 조작을 유한 번 시행하면 1이 될 것이라고 예상하는데, 700,000,000,000보다 작은 모든 짝수에 대해 성립한다는 것이 밝혀져 있긴 하지만, 아직 아무도 증명하지 못했습니다. 유명한 헝가리 수학자 폴 에르되시(Paul Erd' os)는, "우리의 수학은 아직 이 문제를 풀 준비가 되어 있지 않다." 라고 했습니다.

출처: https://codingdojang.com/scode/409?answer_mode=hide

---

[풀이]

def cycle(n):
    i = 1
    while n != 1:
        if n % 2 == 0:
            n /= 2 ; i += 1
        else:
            n = 3*n + 1 ; i += 1
    return i

def max_cycle():
    a = list(map(int, input("입력: ").split()))
    max_cycle = max( [cycle(x) for x in range(a[0],a[1]+1)] )
    print("출력:", a[0], a[1], max_cycle)

max_cycle()

입력: 900 1000
출력: 900 1000 174

먼저 사이클 길이를 만드는 함수를 정의하고 for문으로 입력받은 숫자 사이의 모든 사이클 길이를 구하였다.

---

[추천 풀이]

def cypro(k):
    cl=1
    while k != 1:
        if k%2==0:
            k=k/2
            cl+=1
        else:
            k=3*k+1
            cl+=1
    return cl

i=int(input('INPUT MIN NUM : '))
j=int(input('INPUT MAX NUM : '))
t=0
arw=[]

for t in range(i,j+1):
    arw.append(cypro(t))
print(max(arw))

INPUT MIN NUM : 900
INPUT MAX NUM : 1000
174

i, j를 따로 입력한 점 빼곤 나와 같은 풀이이다.