[백준 *Java] - 1로만들기(1463)

DP 문제를 처음 접했을 때 풀었던 문제입니다. 

일단 DP에 대해서 잘 모르신다면, 아래 링크를 타고 가서 한 번 읽고 오셔도 좋을 거 같습니다.

다이나믹 프로그래밍

점화식

 

 

1로 만들기 문제는 

Top-down, Bottom-up, dfs 방식으로 각기 다르게 문제를 풀어보았습니다.

아래코드 기준으로 메모리,시간 효율이 좋은 순서는

dfs > Bottom-up > Top-down

입니다. 하지만 dfs 와 Bottom-up은 큰 차이는 보이지 않았습니다.

 

각 코드마다 주석으로 코드 설명을 해놓았습니다. 혹시 코드개선할 점과, 모르는 부분이 있으시면 댓글 남겨주시면 감사합니다 : )

 

DP 문제는 종이와 펜을 가지고 일일이 확인을 해보면서 점화식을 찾으며 문제를 풀고 그 능력을 키우면 실력에 도움이 많이 될거 같습니다.

 

 

1. Top-down 방식 👇

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


// Top-down 방식.
// 가장 느림..
public class Boj_1463_topDown {

    private static int[] dpTable;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        dpTable = new int[N + 1];
        System.out.println(makeToOne(N));
    }

    private static int makeToOne(int n) {
        if (n == 1) return 0; // 초깃값은 1~N 까지라, N이 1 일때, 초깃값 0으로 리턴
        if(dpTable[n] > 0) return dpTable[n]; // DP 테이블에 저장되어있는 값들을 리턴해줍니다. '메모이제이션' 또는 '캐싱'이라 불리움.

        dpTable[n] = makeToOne(n - 1)+1; // An = An-1 + 1 을 기본적인 점화식으로 세팅해 둘 수 있다.
        // 위의 점화식이 나올 수 있는 이유를 예시로 들면
        // 4라는 숫자는 3 에다가 '1을 뺀다'라는 조건을 사용하여 최종 1을 만들 수 있어서 그렇다.


        // 이 두 if문 로직은 위의 점화식으로 세팅을 하고도 최소값이 나올 수 있기 때문에 처리를 해줍니다.
        // 즉 점화식은, 최소값을 뽑을 수 있는 식이 아니고
        // 만약 N이 3과 2를 나눌수 있을 시 최소값이 달라기질 수 있기 때문입니다.
        if (n % 3 == 0) {
            int count = makeToOne(n / 3) + 1; // 먼저 3을 나눈 뒤, 3을 나눈 과정이 '1'횟수 증가를 한 부분이기 때문에 +1를 해줍니다.
            if(count < dpTable[n]) dpTable[n] = count;  // 기본 점화식으로 세팅해준 DP 테이블 값과, 위의 3으로 나눌 수 있는 N을 먼저 3으로 나누고 처리한 값과 비교를 합니다.
        }
        if (n % 2 == 0) {
            int count =  makeToOne(n / 2) + 1; // 위와 동일
            if(count < dpTable[n]) dpTable[n] = count;
        }

        return dpTable[n];
    }
}

 

 

2. Bottom-up 방식 👇

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

// Bottom-up 방식.
// 2번째로 빠름,
public class Boj_1463_bottomUp {
    static int [] 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 int[N+1];
        dp[1] = 0; // 1~N 까지면서 '1'은 3가지 조건연산에 해당되지 않으므로 아래 for 문에 제외하기 위해 미리 초기화

        for (int i = 2; i <= N; i++){
            dp[i] = dp[i-1] + 1; // 동적계획법 기본 점화식입니다. An = An-1 +1

            // 기본 점화식을 베이스로 하고,
            // 추가 예외상황인 2,3 으로 나눈 뒤(+1) 그 나눈 값의 DP 테이블 값을 확인하여 기본 점화식과 비교하여 최소값을 찾습니다.
            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[N]);
    }
}

 

 

3. dfs 방식 👇

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

// DFS 로 푼 문제.
// 가장 빠름
public class Boj_1463_dfs {

    static int min;
    public static void dfs(int N, int cnt) {
        if (N == 1) { // 1을 만들려고 하는 부분이니 초기값은 1 입니다. 즉, Depth 가 1일 때는 탐색 stop. 최소값을 리턴을 해주어야합니다.
            min = min > cnt ? cnt : min;
            return;
        }else if (cnt >= min) { // DP 테이블에 저장된 값보다 작을 경우를 리턴 즉, 벌써 최소값이 나왔는데, 추가적 탐색이 필요하지 않음.
            return;
        }

        if (N % 2 == 0)
            dfs(N/2, cnt+1); // 3가지 조건 중 'X 가 2로 나누어 떨어지면 2로 나눈다.'
        if (N % 3 == 0)
            dfs(N/3, cnt+1); // 3가지 조건 중 'X 가 3로 나누어 떨어지면 3으로 나눈다.'

        dfs(N-1, cnt+1); // 3가지 조건 중 '1을 뺀다'
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        min  = Integer.MAX_VALUE;  // 2147483647
        dfs(N, 0); // 매개변수 cnt 로 최소값 카운트를 유지하기 위해 매개변수로 담아 넘깁니다.
        System.out.println(min); // N으로 넘긴 값의 문제의 원하는 해(최소값)가 담겨있습니다.

    }
}

 

 

개선할 점 있다면, 꼭 댓글 남겨주세요.