[백준] 3943번: 헤일스톤 수열(구현, 시뮬레이션)

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

3943번: 헤일스톤 수열

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(bf.readLine());	
		for(int i=0; i<T; i++) {
			int n = Integer.parseInt(bf.readLine());
			int max = n;
			while(n!=1) {
				n = (n%2 == 0) ? n/2 : (n*3)+1;
				max = Math.max(max, n);
			}
			System.out.println(max);
		}
		bf.close();
	}

}

풀이

문제에 맞게 구현해주면 된다.

문제 분류에 DP여서 계속 dp만 생각했는데 ..

그냥 n이 1이 될때까지 짝수면 2로 나누고, 홀수면 3을 곱하고 1을 더하면 된다.

그 후 최댓값을 찾아주면 끝.

 

 

 + System.out.println() 대신 BufferedWriter를 사용하면 시간이 1/3으로 줄어든다.

BufferedWriter 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int T = Integer.parseInt(bf.readLine());	
		for(int i=0; i<T; i++){
			int n = Integer.parseInt(bf.readLine());
			int max = n;
			while(n!=1) {
				n = (n%2 == 0) ? n/2 : (n*3)+1;
				max = Math.max(n, max);
			}
			bw.write(max + "\n");

		}
		bw.flush();
		bw.close();
		bf.close();
	}

}