백준 1463번: 1로 만들기 [DP][다이나믹 프로그래밍] - Java 코드

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

1463번: 1로 만들기

 

 

<백준 1463번: Java코드>

 

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int X = Integer.parseInt(br.readLine());

		int dp[] = new int[X + 1];// dp[x]: x를 만들기 위한 연산 최솟값


		for (int i = 2; i <= X; i++) {

			dp[i] = Math.min(i % 3 == 0 ? dp[i / 3] + 1 : dp[i - 1] + 1,
					Math.min(i % 2 == 0 ? dp[i / 2] + 1 : dp[i - 1] + 1, dp[i - 1] + 1));

		}
		
		System.out.println(dp[X]);

	}

}