https://www.acmicpc.net/problem/1463

모든 가능한 경로 중에서 연산 횟수가 가장 작은 경로를 찾는 최소 비용 탐색 문제다

1. N → N-1
2. N → N/2 (N이 2의 배수일 때)
3. N → N/3 (N이 3의 배수일 때)

각 연산의 비용(cost)은 모두 1이다.

모든 경로를 따라가다 가장 먼저 도착하는 길을 찾는것이 목표

재귀 호출을 통해 각 경우를 돌아 가장 횟수 적은걸 찾음

package src.dataStructure.DP;

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

public class P1463_DP_1 {

    static Integer[] 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 Integer[N + 1]; // 숫자와 인덱스를 1:1로 대응시키기 위해서
        dp[0] = dp[1] = 0;

        System.out.print(recur(N));

    }

    private static int recur(int N) {
        if (dp[N] == null) { // 1 이 될때까지
            // 6으로 나눠지는 경우
            if(N % 6 == 0){
                dp[N] = Math.min(recur(N-1), Math.min(recur(N/3), recur(N/2))) + 1;
                //Math.min 한번에 두개밖에 못해서 3개 씀
            }
            // 3으로만 나눠지는 경우
            else if (N % 3 == 0){
                dp[N] = Math.min(recur(N/3), recur(N-1))+1;
            }
            // 2로만 나눠지는 경우
            else if (N % 2 == 0){
                dp[N] = Math.min(recur(N/2), recur(N-1))+1;
            }
            // 2와 3으로 나눠지는 경우
            else {
                dp[N] = recur(N-1)+1;
            }
        }
        return dp[N];
    }
}

• Math.min() 으로 리턴 값이 가장 작은걸 찾음

package src.dataStructure.DP;

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

public class P1463_DP_2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        System.out.println(recur(N,0));

    }

   private static int recur(int N, int count) {

        // N이 2 미만인 경우 누적된 count값을 반환
        if(N<2){
            return count;
        }
        return Math.min(recur(N/2,count+1+(N % 2)),recur(N/3,count+1+(N % 3)));
    }
}

• 홀수는 바로 /2 못 하니까 짝수 만들려고 -1
• N % 3 == 0 → 바로 /3 가능 → +1
• N % 3 == 1→ -1 한 번 해야 함 → 7 → 6 → 2
• N % 3 == 2→ -1 두 번 해야 함 → 8 → 7 → 6 → 2