Java) 1463번 1로 만들기 (dp)

 

이 문제는 dp를 사용하는 문제입니다.

N부터 시작하여 1까지 내려가는 과정에서

숫자를 만드는데 필요한 횟수를 메모제이션 합니다.

 

1. 1을 빼는 경우를 계산

2. 2로 나누어 떨어지는 경우 1을 뺀 경우와 비교하여 더 작은 값을 찾음.

3. 으로 떨어지는 경우 1을 뺀 경우와 비교하여 더 작은 값을 찾음.

 

각각에서 +1을 하는 경우는 1을 뺀 경우, 2로 나눈 경우, 3으로 나눈 경우를 더해주는 것 입니다.

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n+1];
        dp[0] = dp[1] = 0;
        
        for(int i=2; i<=n; i++) {
            dp[i] = dp[i-1] + 1; // 1을 뺀다.
            if(i % 2 == 0) dp[i] = Math.min(dp[i], dp[i/2] + 1); // 2로 나누어 떨어지는 경우
            if(i % 3 == 0) dp[i] = Math.min(dp[i], dp[i/3] + 1); // 3로 나누어 떨어지는 경우
        }
        System.out.println(dp[n]);
    }
}