[백준/JAVA] 1463번 1로 만들기 - Dynamic Programming

문제

3가지 방법

3으로 나눠지면 3으로 나누고
2로 나눠지면 2로 나누고
위의 2 방법이 안되면 1빼기

풀이

주의점

• 최소 연산 횟수를 구하기 위해 큰 수를 먼저 나누면 안된다.
  ex) 10 (2나누기) -> 5 (1빼기) -> 4 (2나누기) -> 2 (1빼기) -> 1 원하는 계산이 안된다.

예시

점화식의 시작은 2부터이다.
배열 arr[0] = arr[1] = 0으로 초기화 후 시작한다.

arr[2]의 경우 2로도 나눠지지만 문제에서 1보다 큰 값이 N으로 주어지므로, 1을 뺀 값에 1을 더하여 값을 저장한다.

---

arr[3]의 경우 3으로도 나눠진다.
여기서 Math.min(arr[i], arr[i / 3] + 1)이 사용된다. 둘 중 최솟값을 1을 더하여 저장한다.

---

arr[6]의 경우 2와 3 둘 다 나눠진다.
3으로 나눈 값, 2로 나눈 값, 1을 뺀 값 모두 비교해서 최솟값에 1을 더하여 저장한다.

이와 같이 반복하면 arr[9] 까지 값이 저장되고, arr[10]의 경우에는 arr[9] + 1이 최소값이 된다.

코드

코드 해석

가장 먼저 1을 빼고 연산 횟수를 저장한다.
2로 나눠질 때, 또는 3으로 나눠질 때의 경우와 비교해서 더 작은 연산횟수를 가진 값을 저장한다.

제출 코드

import java.io.*;

class Main {

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

        int[] arr = new int[N + 1];

        //arr[0] = 0;
        //arr[1] = 0
        // 점화식은         i=2 부터 시작
        for (int i = 2; i < N + 1; i++) {
            arr[i] = arr[i - 1] + 1;
            if (i % 2 == 0) arr[i] = Math.min(arr[i], arr[i / 2] + 1);
            if (i % 3 == 0) arr[i] = Math.min(arr[i], arr[i / 3] + 1);
        }
        bw.write(String.valueOf(arr[N]));
        bw.flush();
    }
}