[백준/DP] 1463번 1로 만들기 (JAVA)

문제

---

풀이

8달 전에 풀었다가 실패하고 버린 문제 같은데... 왜 버렸지..? 지금은 한 번에 풀었는데 어쨌든 기분은 좋다 ㅎㅎ;;

1. 4부터 n까지 차례로 탐색하며 아래 세 가지 경우를 고려한다. 나누기와 빼기가 같이 있어서 어떤 것이 최솟값일지 보장할 수 없기 때문에 모두 고려해야 한다.
   • i가 3으로 나눠지면 최솟값과 dp[i/3]를 비교하고 갱신
   • i가 2로 나눠지면 최솟값과 dp[i/2]를 비교하고 갱신
   • 최솟값과 dp[i-1]를 비교하고 갱신
2. 위 세 가지 경우 중 최솟값에 연산횟수 1을 더하고 dp[i]에 저장한다.

코드

import java.io.*;

public class Main {

    private static final int MAXIMUM = 1000000;

    private static int n;
    private static int[] dp = new int[MAXIMUM + 1];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        dp();
        bw.append(Integer.toString(dp[n]));

        br.close();
        bw.close();
    }

    private static void dp() {
        dp[1] = 0;
        dp[2] = 1;
        dp[3] = 1;
        for (int i = 4; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            if (i % 3 == 0) min = Math.min(min, dp[i / 3]);
            if (i % 2 == 0) min = Math.min(min, dp[i / 2]);
            min = Math.min(min, dp[i - 1]);
            dp[i] = min + 1;
        }
    }
}