[알고리즘] 1463. 1로 만들기

0. 문제

 

1463번: 1로 만들기

 

---

1. 문제 이해

 

1. Brute force
2. DP

 

---

2. 제출

 

가. Brute force

import java.util.Scanner;

// brute force -> 144ms
public class BOJ1463 {
    static int N, ret = Integer.MAX_VALUE; // 입력받은 수
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        solve(N, 0);

        System.out.println(ret);
        sc.close();
    }

    static void solve(int num, int cnt) {
        if(cnt > ret) return;
        if(num == 1) {
            ret = Math.min(ret,  cnt);
            return;
        }

        if(num%3==0) solve(num/3, cnt+1);
        if(num%2==0) solve(num/2, cnt+1);
        solve(num-1, cnt+1);
    }
}

 

---

나. DP

 

1) 하향식 DP

• 재귀 함수로 구현

import java.util.Arrays;
import java.util.Scanner;

// 하향식 DP -> 142ms
public class BOJ1463 {
    static int N, ret = Integer.MAX_VALUE; // 입력받은 수
    static int[] dp;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        // dp 초기화
        dp = new int[N+1];
        Arrays.fill(dp,  Integer.MAX_VALUE);

        ret = solve(N);

        System.out.println(ret);
        sc.close();
    }

    static int solve(int num) {
        //if(cnt > ret) return;
        if(num == 1) {
            return 0;
        }

        // 중복된 계산을 방지한다.
        if(dp[num] != Integer.MAX_VALUE) {
            return dp[num];
        }

        // 최초 1회 실행
        int min = Integer.MAX_VALUE;
        if(num%3==0) min = Math.min(min, solve(num/3) + 1);
        if(num%2==0) min = Math.min(min, solve(num/2) + 1);
        min = Math.min(min,  solve(num-1)+1);

        return dp[num] = min;
    }
}

 

---

2) 상향식 DP

• 반복문으로 구현

import java.util.Arrays;
import java.util.Scanner;

// 상향식 DP -> 140ms
public class BOJ1464_2 {
    static int N, ret = Integer.MAX_VALUE; // 입력받은 수
    static int[] dp;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        // dp 초기화
        dp = new int[N+1]; // i까지의 수의 최소 연산 횟수
        Arrays.fill(dp,  Integer.MAX_VALUE);

        dp[1] = 0; // 기저 조건
        for(int i=2, end=N+1; i<end; i++) { // 2부터 N까지 최소 연산 횟수를 구한다.
            // 저장된 계산 결과 활용
            dp[i] = dp[i-1] + 1;
            if(i%3==0) dp[i] = Math.min(dp[i], dp[i/3] + 1);
            if(i%2==0) dp[i] = Math.min(dp[i], dp[i/2] + 1);
        }

        System.out.println(dp[N]);
        sc.close();
    }
}

 

---

 

DP가 무조건 빠른 것은 아니다.