[백준 알고리즘] 백준 14920번 3n+1 수열 자바(JAVA)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 14920번 3n+1 수열 자바(JAVA)

1) 문제번호 : 14920번

 

2) 문제 출처

https://www.acmicpc.net/problem/14920

14920번: 3n+1 수열

 

2. 문제

다음의 점화식에 의해 정해지는 수열 C(n)을 생각하자:

     C(n+1) = C(n)/2     (C(n)이 짝수일 때)
            = 3*C(n)+1   (C(n)이 홀수일 때)

초항 C(1)이 자연수로 주어지면, 이 점화식은 자연수로 이루어지는 수열을 정한다.  예를 들어, C(1)=26이면, 다음의 수열이 된다.

26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, ...

이 경우, 수열의 뒷부분은 4, 2, 1 이 끝없이 반복된다. 실제로 C(1)이 5×260보다 작은 자연수인 모든 수열은 언젠가는 4, 2, 1로 끝나게 된다는 것이 알려져 있다.

주어진 입력 C(1)에 대하여 C(n)이 처음으로 1이 되는 n을 출력하시오.

 

3. 제약사항

 

4. 입력

C(1); 1 ≤ C(1) ≤ 100000

 

5. 출력

C(n)이 처음으로 1이 되는 n

 

6. 풀이

- 값을 입력받고, N 값이 1이라면 1만 출력하고 끝낸다.

- N이 1이 아니라면 TN으로 값처리를 한 값을 TN으로 설정하고, 마지막에 N에 TN값을 넣는다.

- 그래서, N이 짝수, 홀수에 따라 분기 처리를 하여 점화식에 의거하여 값을 구한다.

 

7. 소스 코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		if(N == 1) {
			System.out.println(1);
		} else {
			int cnt = 1;
			int TN = 0;
			
			while(true) {
				
				if(TN == 1) {
					System.out.println(cnt);
					break;
				}
				
				if(N % 2 == 0) {
					TN = N / 2;
				} else {
					TN = (3 * N) + 1;
				}
				
				N = TN;
				cnt++;
			}
			
		}
		
	}
}

---