[CLASS 3: DP] 백준 1463 1로 만들기

1463번: 1로 만들기

https://www.acmicpc.net/problem/1463

 

# 코드

import java.io.*;

public class Main {
    static Integer[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        dp = new Integer[n + 1];
        dp[0] = dp[1] = 0;

        System.out.print(recur(n));
    }

    static int recur(int n) {
        if (dp[n] == null) {
            // 6으로 나눠지는 경우
            if (n % 6 == 0) {
                dp[n] = Math.min(recur(n - 1), Math.min(recur(n / 3), recur(n / 2))) + 1;
            }
            // 3으로만 나눠지는 경우
            else if (n % 3 == 0) {
                dp[n] = Math.min(recur(n / 3), recur(n - 1)) + 1;
            }
            // 2로만 나눠지는 경우
            else if (n % 2 == 0) {
                dp[n] = Math.min(recur(n / 2), recur(n - 1)) + 1;
            }
            // 2와 3으로 나누어지지 않는 경우
            else {
                dp[n] = recur(n - 1) + 1;
            }
        }
        return dp[n];
    }
}

• 6으로 나눠지는 경우는 3으로 나누는 경우와 2로 나누는 경우, 1을 빼는 경우 모두 재귀호출 하여 3가지 경우 중 최솟값으로 DP를 갱신해야 하고, 3으로만 나눠지는 경우는 3으로 나누는 경우와 1을 빼는 경우를 재귀호출, 2로만 나눠지는 경우는 2로 나누는 경우와 1을 빼는 경우의 수를 재귀호출, 그 외에는 1을 빼는 경우만 재귀호출을 해주면 된다고 한다.

 

아래는 DP가 아닌 재귀를 이용해 푸는 코드이다.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        System.out.println(recur(n, 0));
    }

    static int recur(int n, int count) {
        // n이 2 미만인 경우 누적된 count값을 반환
        if (n < 2) {
            return count;
        }
        return Math.min(recur(n / 2, count + 1 + (n % 2)), recur(n / 3, count + 1 + (n % 3)));
    }
}

• 재귀 호출 할 때 같이 연산 횟수를 같이 갱신시키는 방법이다. n=1 이 되기 전 까지 count를 누적했다가 1이 되면 누적된 count를 반환하여 재귀를 탈출시킨다.

 

두 코드 모두 아래 블로그를 참고했다. DP의 길은 멀고도 험하다. .·´¯`(>▂<)´¯`·. 

[백준] 1463번 : 1로 만들기 - JAVA [자바]