메뉴 건너뛰기

문제

00a16 우박수 구하기    0  

시간메모리제출 올바른 답 비율
1초64MB
1429
420
29.4%


나의 횟수나의 최근 판정시도 성공 비율
371328
88.4%
우박수 구하기  

입력받은 자연수 n의 우박수와 우박수 사이클을 구하는 프로그램을 작성하시오.

우박수는 다음의 알고리즘을 통해 구할 수 있으며, 우박수 사이클은 알고리즘을 통해 출력되는 우박수의 개수를 의미한다.

‘우박수’는 다음의 알고리즘을 통해 출력되는 값의 크기가 커졌다가 작아지는 현상이 반복되다가 종국에 가서는 1이 되어 종료된다는 의미에서 유래되었다.

<알고리즘>

자연수 n을 입력받는다.
n이 1이 될 때까지 다음을 반복한다.
   n을 출력한다.    
   만약 n이 홀수면      
      n에 3n+1을 저장한다.    
   그렇지 않으면
      n에 n/2를 저장한다.
n을 출력한다.

자연수 n이 22이면, 우박수는 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 이다. 이때 우박수 사이클은 16이다.

입력

첫째 줄에 1,000,000 미만의 자연수 n이 주어진다.

출력

첫째 줄에 입력받은 자연수의 우박수 사이클을 출력한다. 두 번째 줄에 공백을 사이에 두고 우박수를 출력한다. 우박수의 최대 사이클은 1000 미만이라고 가정한다.

예시
1입력
22
출력
16
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
2입력
19
출력
21
19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
위로