[JAVA/dp]백준 1463 : 1로 만들기

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

 

1. 주어진 수 n이 1이 되기 위한 최소 경로의 수를 담아주는 배열 지정. 

dp[n] = x 면 n이 1이 되기 위한 최소 경로의 수 x를 뜻함. 

그렇기 때문에 dp의 길이는 dp[n+1] 로 지정해야함.(0이 들어가니까)

 

2. dp[0] 과 dp[1]은 0이 됨. 

 

3. 2부터 n까지 반복(n포함)

 

4. 처음 dp[i]는 전의 경로의 수에서 +1 한 만큼 (i-1 +1 = i 이기 때문에 ) 설정해줌 (-1 수식 반영)

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

 

5.2로 나눠지는지 3으로 나눠지는지에 따라서 나눈 몫의 경로의 수 + 몫까지 간 경로 1 

dp[i] = dp[i/2] + 1 

 

6. 4번과 5번의 경로의 수를 비교하여 작은 수를 대입해줌 

 

import java.io.*;

public class Main {

	static int[] dp;
    
    public static void main(String[] args) throws IOException{
    
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        br.close();
        
        dp = new int[n+1];
        
        for(int i=2; i<=n ; i++){
        
        	dp[i] = dp[i-1]+1;
            
            if(i%3 == 0) dp[i] = Math.min(dp[i/3]+1,dp[i]);
 			
            if(i%2==0) dp[i] = Math.min(dp[i/2]+1, dp[i]);
       
        }
        
        System.out.println(dp[n]);
    
    }

}