2016/01/31 코드그라운드 2016 SCPC 예선1차 : 3N+1

https://www.codeground.org/practice/practiceProbView.do?probId=25

해석 요약 : 3N+1 문제, 함수 F를 적용시켰을 때 2^60 이하의 모든 정수들은 1로 도달할 수 있다는 게 증명되었다. 함수 F를 K 번 적용했을 때 1이 되는 숫자중 가장 큰 수와 가장 작은 수를 구하자.

생각할 것 :
1. 제일 큰 수는 2^K
2. 결국엔 2의 지수승 형태가 되어야 함수 F로 1에 도달할 수 있다.
3. 홀수*3은 (홀수)*(2+1)이므로 짝수+홀수=홀수이다. 따라서 3N+1을 한 후엔 반드시 짝수가 되게 되어있다.
4. F(c)=k가 될 수 있는 방법은 F(x)=k-1 인 숫자x가 2배가 되거나 (x-1)/3 이 된 숫자이다.
F(x)=k
k값에 따라 -> 나올 수 있는 x
k=0 -> 1 (문제에서 이렇게 정의함)
k=1 -> 2
k=2 -> 4
k=3 -> 8
k=4 -> 16
k=5 -> 32 5
이제 가지치기를 하면 된다. 각 숫자 왼쪽으로 가는 가지는 2배, 오른쪽으로 가는 가지는 3으로 나눈 나머지가 1일 경우면서 짝수일 때에만 생성되며 값은 (x-1)/3
k=6 -> 64 10
k=7 -> 128 20 3
k=8 -> 256 40 6
k=9 -> 512 85 80 13 12
k=10 -> 1024 170 (28) 160 26 (4) 24
여기서 보면 k=9 인 13에서 k=10 인 4를 계산할 수 있다. 근데 4는 k=2였던 값이고 2의 승수이므로 빼야된다. 85는 3N+1이지만 홀수니까 28이 나올 수 없다.
k=11 -> 2048 341 340 320 53 52 48
k=12 -> 4096 682 680 113 640 106 104 17 96
작은 숫자만 저장하면 안된 다는걸 보여준다. 한참 전에 분기했던 두 번째로 큰 수인 52가 17이 되고 가장 작았던 48은 96이 되버린다.