[백준] 1463. 1로 만들기 (Java)

 

문제

1463번: 1로 만들기

 

알고리즘

다이나믹 프로그래밍(DP)

 

풀이

3가지 연산이 있을 때,

어떤 정수 X을 만드는 횟수의 최솟값을 make[X] 라고 한다면 그 값은 다음 세 값 중 최솟값일 것이다.

1. make[X / 3] + 1   (나누어 떨어지면)
2. make[X / 2] + 1   (나누어 떨어지면)
3. make[X - 1] + 1

따라서 2부터 X까지 위 연산을 적용하고, make[X]를 출력하면 된다.

 

 

 

코드

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

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());
		int[] dp = new int[N + 1];
		dp[1] = 0;

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

			dp[i] = dp[i - 1] + 1;

			if (i % 2 == 0 && dp[i / 2] + 1 < dp[i])
				dp[i] = dp[i / 2] + 1;

			if (i % 3 == 0 && dp[i / 3] + 1 < dp[i])
				dp[i] = dp[i / 3] + 1;
		}

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