[백준] 1463 - 1로 만들기

백준 바로가기

1463번: 1로 만들기

DP(Dynamic Programming) 알고리즘 문제를 풀고 있는데요, DP로 안풀고 저만의 방식으로 풀다가 계속 틀리는 바람에 다른 분들 블로그 보고 DP 방식으로 풀었더니 됩니다. 두 가지 방법으로 풀 수 있는데 반복문 사용은 Bottom-up, 재귀 메서드를 이용한 방법은 Top-down으로 불립니다. 재귀의 경우 DP 배열을 써도 느리니 반복문 사용한 Bottom-up 방법을 추천합니다. 일단 두 가지 방법 모두 다루겠습니다.

문제 들어가기에 앞서 사고의 전환이 필요했습니다. 저는 주어진 N으로부터 3을 최대한 많이 사용해 1로 만드는 로직을 만든 다음 반복문을 돌리려고 했습니다. 하지만 풀이를 보면 1,2,3,...N-1까지 N보다 작은 수들이 1로 만들어지는 최소 횟수를 DP 배열에 저장한 다음 N/3, N/2, N-1일 때 최소 횟수 중 min 값을 골라 출력하는 방식으로 접근했습니다. 세 가지 경우 1회만 사용하여 N을 만들수 있기 때문입니다.

즉 DP의 핵심은 작은 문제들을 풀어가면서 데이터를 DP 배열에 저장한 다음 본 문제를 해결하는 데에 있습니다. 

1) Bottom-up (반복문)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    static int[] dp;
    static int x;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        x = Integer.parseInt(br.readLine());
        dp = new int[x + 1];
 
        dp[0] = 0;
        dp[1] = 0;
        //Bottom-up
        for (int i = 2; i <= x; i++) {
            dp[i] = dp[i - 1] + 1;
            if (i % 2 == 0)
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            if (i % 3 == 0)
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
        }
        System.out.println(dp[x]);
        br.close();
    }
}
 

2) Top-down (재귀 메서드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    static int[] dp;
    static int x;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        x = Integer.parseInt(br.readLine());
        dp = new int[x + 1];
        
        //Bottom-up
//        for (int i = 2; i <= x; i++) {
//            dp[i] = dp[i - 1] + 1;
//            if (i % 2 == 0)
//                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
//            if (i % 3 == 0)
//                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
//        }
        System.out.println(dp(x));
        br.close();
    }
    
    public static int dp(int n) {
        if (n == 1)
            return 0;
        if (dp[n] > 0)
            return dp[n];
        dp[n] = dp(n - 1) + 1;
        if (n % 3 == 0)
            dp[n] = Math.min(dp[n], dp[n / 3] + 1);
        if (n % 2 == 0)
            dp[n] = Math.min(dp[n], dp[n / 2] + 1);
        
        return dp[n];
    }
}