[백준 1463] 1로 만들기

처음 문제를 봤을때는 그리디 문제인줄

하지만 예제를 보면 그리디로 풀면 안된다는걸 알 수 있다

 

무조건 3으로 나누는게 좋고 1로 나누는게 제일 안좋다는 생각이 먼저 드는데

10을 보면 10 - 9 - 3 - 1 로 3번만에 걸쳐서 할 수 있는걸

그리디로 풀면 10 - 5 - 4 - 2 - 1 이렇게 4번 걸린다

그래서 dp로 풀어야한다

 

이건 자바 연습겸 자바로 품

 

---

import java.io.*;

public class Main {

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

        int[] dp = new int[1000001];

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

        dp[1] = 0;
        dp[2] = 1;
        dp[3] = 1;

        int n1, n2, n3;
        for(int i=4;i<=N;i++){
            n1 = dp[i-1];
            n2 = (i%3==0 ? dp[i/3] : n1);
            n3 = (i%2==0 ? dp[i/2] : n1);

            dp[i] = Math.min(n1, Math.min(n2,n3)) + 1;
        }

        System.out.print(dp[N]);
    }
}