[백준] 1463 1로 만들기(Silver.3) - DP(동적 계획법)

문제

코드

시도 1 - X(시간 초과)

처음엔 완전 탐색을 이용하여 모든 경우의 수를 구하는 방법을 생각했다. 아래 그림과 같이 HashMap에 Memoization을 저장하고 원하는 조건이 나오면 탈출하는 방식으로 구현했다.

그래프를 그려보면 아래와 같다.

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

public class _1463_1로_만들기 {
    static int minCnt = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        // 1순위: /3, 2순위: /2, 3순위: -1

//        int[][] memo = new int[n+1][3];
        HashMap<Integer, int[]> memo = new HashMap<>();
        dp(n, memo, 0);
        System.out.println(minCnt);

    }

    // 하향식 방법 사용
    public static void dp(int x, HashMap<Integer, int[]> memo, int cnt) {
        if (x == 0) {
            return ;
        }
        if (x == 1) {
            minCnt = Math.min(minCnt, cnt);
            return ;
        }

        // 계산 된 부분 문제인 경우
        if (memo.containsKey(x)) {
            if (memo.get(x)[0] != 0) dp(memo.get(x)[0], memo, cnt+1);
            if (memo.get(x)[1] != 0) dp(memo.get(x)[1], memo, cnt+1);
            if (memo.get(x)[2] != 0) dp(memo.get(x)[2], memo, cnt+1);
        }

        // 아직 계산을 안한 부분 문제인 경우
        else {
            int[] arr = new int[3];
            if (x % 3 == 0) arr[0] = x / 3;
            if (x % 2 == 0) arr[1] = x / 2;
            arr[2] = x - 1;

            memo.put(x, arr);
            dp(arr[0], memo, cnt+1);
            dp(arr[1], memo, cnt+1);
            dp(arr[2], memo, cnt+1);
        }
    }
}

그런데 이 방법은 이미 계산된 부분 문제도 중복 호출이 되기 때문에 시간 초과가 난다. 잘 모르겠기도 하고 DP 문제는 처음 접해보기 때문에 연습 겸 ChatGPT의 도움을 받았다.

시도 2 - O

하향식 접근 방법을 이용하여 재귀로 풀 거라 생각했는데 상향식 방법으로 풀 수 있었다.
-1 연산, /2 연산, /3 연산을 순서대로 진행한 뒤 최소 연산 횟수를 memo 배열에 저장하며 부분 문제를 해결하는 방식이다.

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

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

        // DP 배열 선언 및 초기화
        int[] memo = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            memo[i] = memo[i - 1] + 1; // 기본 연산 (x - 1)
            if (i % 2 == 0) memo[i] = Math.min(memo[i], memo[i / 2] + 1);
            if (i % 3 == 0) memo[i] = Math.min(memo[i], memo[i / 3] + 1);
        }

        // 결과 출력
        System.out.println(memo[n]);
    }
}

DP 계산 과정

• i = 2:
  • 기본 연산: memo[2] = memo[1] + 1 = 1
  • 2 % 2 == 0: memo[2] = Math.min(memo[2], memo[1] + 1) = 1
  • 2 % 3 != 0: 업데이트 없음.
• i = 3:
  • 기본 연산: memo[3] = memo[2] + 1 = 2
  • 3 % 2 != 0: 업데이트 없음.
  • 3 % 3 == 0: memo[3] = Math.min(memo[3], memo[1] + 1) = 1
• i = 4:
  • 기본 연산: memo[4] = memo[3] + 1 = 2
  • 4 % 2 == 0: memo[4] = Math.min(memo[4], memo[2] + 1) = 2
  • 4 % 3 != 0: 업데이트 없음.
• i = 5:
  • 기본 연산: memo[5] = memo[4] + 1 = 3
  • 5 % 2 != 0: 업데이트 없음.
  • 5 % 3 != 0: 업데이트 없음.
• i = 6:
  • 기본 연산: memo[6] = memo[5] + 1 = 4
  • 6 % 2 == 0: memo[6] = Math.min(memo[6], memo[3] + 1) = 2
  • 6 % 3 == 0: memo[6] = Math.min(memo[6], memo[2] + 1) = 2
• i = 7:
  • 기본 연산: memo[7] = memo[6] + 1 = 3
  • 7 % 2 != 0: 업데이트 없음.
  • 7 % 3 != 0: 업데이트 없음.
• i = 8:
  • 기본 연산: memo[8] = memo[7] + 1 = 4
  • 8 % 2 == 0: memo[8] = Math.min(memo[8], memo[4] + 1) = 3
  • 8 % 3 != 0: 업데이트 없음.
• i = 9:
  • 기본 연산: memo[9] = memo[8] + 1 = 4
  • 9 % 2 != 0: 업데이트 없음.
  • 9 % 3 == 0: memo[9] = Math.min(memo[9], memo[3] + 1) = 2
• i = 10:
  • 기본 연산: memo[10] = memo[9] + 1 = 3
  • 10 % 2 == 0: memo[10] = Math.min(memo[10], memo[5] + 1) = 3
  • 10 % 3 != 0: 업데이트 없음.
• 결과: memo = [0, 1, 1, 1, 2, 3, 2, 3, 3, 2, 3]