[실버3, DP] 백준 1463 - 1로 만들기 (자바)

Think

1. 구현 방법 접근을 dp로 떠올릴 수 있는 단계는 아직 아닌거같다.. 그래서 https://st-lab.tistory.com/133 참고함.

2. 처음에는 풀이가 이해가 안됐는데, 이해가 되니 너무 신기하고 재밌다. 세상 사람들 참 똑똑하다

3. 아직 실버 3인데 하하.. dp는 정말 많이 풀어봐야겠다

 

제출코드 1 (DP와 재귀 활용)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n;
    static Integer dp[];

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        init();
        progress();
    }

    private static void progress() {
        dp = new Integer[n+1];
        dp[0] = dp[1] = 0;

        System.out.println(recursion(n));
    }

    private static int recursion(int number) {

        // 아직 값이 안구해졌으면,
        if(dp[number] == null){
            if(number % 6 == 0){
                dp[number] = Math.min(recursion(number/3), Math.min(recursion(number/2), recursion(number-1))) + 1;
            }else if(number % 3 == 0){
                dp[number] = Math.min(recursion(number/3), recursion(number-1)) + 1;
            }else if(number % 2 == 0){
                dp[number] = Math.min(recursion(number/2), recursion(number-1)) + 1;
            }else{
                dp[number] = recursion(number-1) + 1;
            }
        }

        return dp[number];
    }


    private static void init() throws IOException {
        n = Integer.parseInt(br.readLine());
    }

}

 

 

제출코드 2 (재귀)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n;
    static Integer dp[];

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        init();
        progress();
    }

    private static void progress() {
        dp = new Integer[n+1];
        dp[0] = dp[1] = 0;

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

    private static int recursion(int number, int count) {
        if(number < 2){
            return count;
        }

        return Math.min(recursion(number / 3, count+1+(number%3)), recursion(number/2, count + 1+(number%2)));
    }


    private static void init() throws IOException {
        n = Integer.parseInt(br.readLine());
    }

}