[백준 알고리즘] (DP) 1463번 Java 풀이

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

출처: https://plzrun.tistory.com/entry/알고리즘-문제풀이PS-시작하기 [plzrun's algorithm]

 

백준 알고리즘 1463번

 

change Nxxxx -> Main && remove package lines!!!

이클립스에서 작성하면서 문제 이름으로 클래스를 생성하여 풀었기 때문에

클래스 이름을 Main으로 바꾸고, package 부분도 지우고 제출해야 정상적으로 돌아갑니다.

 

<풀이> - Bottom up

package dp;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class N1463 {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        int dp[] = new int[num+1]; //입력 값보다 하나 더 큰 사이즈로 생성
        dp[0] =0;
        dp[1] =0;
        
        for(int i =2; i<= num; i++) {
            dp[i] = dp[i-1] +1 ;
            if(i%2 ==0) dp[i] = Math.min(dp[i], dp[i/2]+1);
            if(i%3 ==0) dp[i] = Math.min(dp[i], dp[i/3]+1);
        }
        
        System.out.println(dp[num]);
        br.close();
    }
 
}