백준_1463 1로 만들기 (DP)

 

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

public class BJ_1463_1로만들기 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] d = new int[n+1];
        d[1] = 0;

        for (int i=2; i<n+1; i++) { //3가지 연산의 경우 중 최소값을 구해야한다
            d[i] = d[i-1] + 1;
            if (i%3 == 0) {
                d[i] = Math.min(d[i], d[i/3] + 1);
            }

            if (i%2 == 0) {
                d[i] = Math.min(d[i], d[i/2] + 1);
            }
        }

        System.out.println(new StringBuilder().append(d[n]));
    }

}

1463번: 1로 만들기