DP :: 백준 :: 1로 만들기 :: 1463

1로 만들기 1463

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

[풀이방법]

dp[i] = i를 1로 만드는 최소 연산 수

dp[i] = min(dp[i-1], dp[i/2], dp[i/3])+1

모든 연산을 마친 후 dp[i]를 출력하면 답!

import java.util.Scanner;
/*
 * X가 3으로 나누어 떨어지면, 3으로 나눔.
 * X가 2로 나누어 떨어지면, 2로
 * 1을 뺀다.
 * 범위 : 1<=X<=1000000
 */
public class Main {
    static int[] ar = new int[1000001];
 
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        Scanner scn = new Scanner(System.in);
        int a = scn.nextInt();
 
        int tmp1, tmp2, tmp3;
        for (int i = 2; i <= a; i++) {
            tmp1 = 0;
            tmp2 = Integer.MAX_VALUE;
            tmp3 = Integer.MAX_VALUE;
            tmp1 = ar[i - 1] + 1;
            if (i % 2 == 0) {
                tmp2 = ar[i / 2] + 1;
            }
            if (i % 3 == 0) {
                tmp3 = ar[i / 3] + 1;
            }
            ar[i] = Math.min(tmp1, Math.min(tmp2, tmp3));
        }
 
        System.out.println(ar[a]);
    }
}

!!주의!!

무조건 나눈다고 답이 나오는건 아니다..

예를 들어 10을 2로 먼저 나눈다면

10 -> 5 -> 4 -> 2 -> 1

이렇게 4번이 걸린다.