[BOJ] 1463 1로만들기 (Java)

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

알고리즘

DP

풀이

1. 자기보다 1작은 값일 때의 연산횟수보다 1만큼 큰 값으로 초기화한다.
2. 만약 자신이 3으로 나눠진다면, 3으로 나눈 값일 때의 연산횟수와 1번 과정에서의 값을 비교한다.
3. 만약 자신이 2로 나눠진다면, 2로 나눈 값일 때의 연산횟수와 2번 과정에서의 값을 비교한다.

코드

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

public class Main_1463_1로만들기 {
	
	static int N, dp[];
	
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
	
		N = sc.nextInt();
		dp = new int[N+1];
		
		for(int i=2; i<=N; i++) {
			dp[i] = dp[i-1]+1;									// i-1 일떄의 값에 1만 더해서 초기값 저장 (1 뺴는 연산이 하나 추가된 것)
			if(i%3 == 0) dp[i] = Math.min(dp[i], dp[i/3]+1);	// 만약 3으로 나눠진다면 i/3의 연산횟수에 1을 더한 것 중에 작은 값으로 업데이트  
			if(i%2 == 0) dp[i] = Math.min(dp[i], dp[i/2]+1);	// 만약 2로 나눠진다면 i/2의 연산횟수에 1을 더한 것 중에 작은 값으로 업데이트 
		}
		
		System.out.println(dp[N]);
		sc.close();
	}
	
}