[백준 baekjoon] 1463번 1로 만들기 (동적 계획법 dp) 자바 Java 풀이

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

• X가 3으로 나누어 떨어지면, 3으로 나눈다.
• X가 2로 나누어 떨어지면, 2로 나눈다.
• 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

풀이

import java.io.*;
import java.util.*;

class Main {

    public static int[] dp;


    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());

        dp = new int[N];
        Arrays.fill(dp, -1);

        dp[0] = 0;

        bw.write(String.valueOf(dfs(N)));


        bw.flush();

        bw.close();
    }


    public static int dfs(int N) {


        if (dp[N - 1] != -1) return dp[N - 1];


        if (N % 6 == 0) {
            dp[N - 1] = Math.min(dfs(N - 1), Math.min(dfs(N / 3), dfs(N / 2))) + 1;
        } else if (N % 3 == 0) {
            dp[N - 1] = Math.min(dfs(N / 3), dfs(N - 1)) + 1;
        } else if (N % 2 == 0) {
            dp[N - 1] = Math.min(dfs(N / 2), dfs(N - 1)) + 1;
        } else {
            dp[N - 1] = dfs(N - 1) + 1;
        }
        return dp[N - 1];
    }


}

실수 모음

• dp 배열 초기값을 설정하지 않았다. 초기 인덱스에 대해 값을 미리 설정해야 한다.
• 메모이제이션을 위해 dp 배열을 초기화 할 때 팁
  • int 배열의 경우 -1로 초기화하여 여전히 -1값을 가지고 있는지 확인함으로써 메모이제이션을 수행했다.
  • 다른 방법은 dp 배열을 Integer 타입으로 선언하고 null 여부를 체크하는 것이다.
• Math.min 메서드의 파라미터로 두 개의 dfs 함수를 넘긴다면, 어떤 함수를 먼저 두는 것이 더 효율적인지 생각해볼 필요가 있다.
• 처음에는 cnt 변수를 dfs 함수의 매개변수로 넘기며(1씩 증가시키며) N이 1이 되었을 때 cnt 값을 반환하여 dp 배열에 저장했다. 이 방법으로 하면 제대로 된 결과가 나오지 않는다. 이유는 아직 모르겠다.