링크

1로 만들기

문제

풀이

dp가 n만큼 진행한다
1에서 부터 시작해서 n으로 간다
그래서 dp[i] = dp[i-1] + 1;을 먼저 실행하고 만약 3이나 2로 나눠지면 각각 dp[i/3] + 1과 dp[i/2] + 1을 수행하면 된다.
주의할점은 3과 2를 나눴을때 둘다 만족하는 경우가 6의 배수이므로 if else가 아닌 if if문으로 검사해줘야된다.

코드

import java.util.*;

public class Main{
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int X = sc.nextInt();
        int[] dp = new int[X+1];

        for(int i=2;i<dp.length;i++){
            dp[i] = dp[i-1] + 1;
            if(i % 3 == 0) dp[i] = Math.min(dp[i], dp[i/3] + 1);
            if(i % 2 == 0) dp[i] = Math.min(dp[i], dp[i/2] + 1);
        }

        System.out.println(dp[X]);

    }
}