백준 1463 1로 만들기 JAVA (DP)

1. 문제

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

1463번: 1로 만들기

 

2. 설명

문제에 설명되어 있는 조건에 따라 최솟값을 구하고, min 배열에 저장했다.

bottom-up 방식 사용

DP에서 가장 어려운게 (내기준) 점화식 규칙을 뽑아내는 건데 이 문제는 문제에서 말해줘서 쉬웠다.

 

3. 코드

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int[] min = new int[1000001]; // N <= 10^6
		
		min[1] = 0;
		for(int i=2; i<=N; i++) {
			min[i] = min[i-1] + 1; // 조건 3
			if(i%2==0) min[i] = Math.min(min[i], min[i/2] + 1); // 조건 2
			if(i%3==0) min[i] = Math.min(min[i], min[i/3] + 1); // 조건 1
		}
		
		System.out.println(min[N]);
	}
}