[백준] 1로 만들기

- 간단한 dp 문제

- 하지만 못 품

 

- 필요 아이디어

- dp[i] => i의 숫자의 경우에 필요한 최소 단계 수

 

import java.util.Scanner;
public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int[] dp = new int[a+1];
        dp[1] = 0;
        for(int i=2; i<=a; 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[a]);
    }
}