[Silver III][JAVA]1463번:1로 만들기

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.

풀이

최소 연산 횟수
2의 경우엔 2 2→1 1번 만에 만들 수 있다.
10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다.

적용 방법

1. Top-Down : 재귀함수 사용
2. Bottom-Up : 반복문 사용(✅)

점화식

(-1)
dp[i] = dp[i-1] + 1;// +1은 연산을 수행한 카운터를 하나 올려줌

(% 3)
dp[i] = Math.min(dp[i], dp[i/3] + 1);// 나누기 3 연산 수행할 경우와 -1 연산 수행한 경우 비교

(% 2)
dp[i] = Math.min(dp[i], dp[i/2] + 1);// 나누기 3 연산 수행할 경우와 -1 연산 수행한 경우 비교

코드

package baekjoon_java.SilverIII;

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

public class 일로만들기 {//1463번 dp
    static int N;
    static Integer[] dp;

    public static void main(String[] arg) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        dp = new Integer[N + 1];

        dp[1] = 0;//dp초기화

        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + 1;// +1은 연산을 수행한 카운터를 하나 올려줌

            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);// 나누기 3 연산 수행할 경우와 -1 연산 수행한 경우 비교
            }
            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);// 나누기 3 연산 수행할 경우와 -1 연산 수행한 경우 비교
            }
        }
        System.out.println(dp[N]);
    }

}