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

[BOJ] 1463. 1로 만들기

📌 풀이 과정

목표는 숫자 X에서 1까지 가는 최소한의 연산 횟수를 구하는 것이다.
각 숫자에 대해 연산을 할 수 있는 경우를 고려해서 최소 연산 횟수를 저장해야 한다.

이 과정을 상향식(bottom-up)으로 풀 수 있으며, 메모이제이션을 통해 중복 계산을 피해 효율을 높일 수 있다.

가능한 연산

• 1을 빼기
• 2로 나누기 (2로 나누어 떨어지는 경우)
• 3으로 나누기 (3으로 나누어 떨어지는 경우)

📝 예시: X = 5의 경우

5는 2나 3으로 나누어 떨어지지 않는다.
무조건 1을 빼서 4로 만들어야 하는데, 이때 dp[5] = dp[4] + 1 식이 도출된다.

여기서 dp[4]는 4를 1로 만드는 최소 연산 횟수이기에
dp[4]에다가 1을 더하게 되면, 5에서 4로 가는 연산을 추가한 횟수가 된다.

즉, dp[i] = dp[i-1] + 1은 숫자에서 1을 빼는 연산을 한 번 더한 경우의 최소 연산 횟수를 의미하는 것을 알 수 있다.

📝 예시: 숫자가 2나 3으로 나누어 떨어지는 경우

나누는 것이 더 효율적인 경우가 있을 수 있다. 그래서, 1을 빼는 방법과 2나 3으로 나누는 방법 중 최소 연산 횟수를 선택하는 방식 중 최소 연산 횟수를 선택하면 된다.

✨ 제출 코드

import java.util.Scanner;

public class 숫자1로만들기_1463 {
	
	static int N;
	static int[] dp;
	
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	N = sc.nextInt();
    	dp = new int[N + 1];
    	
    	for(int i = 2; i < N + 1; i++) {
    		
    		// 현재의 수에서 1을 빼는 경우
    		dp[i] = dp[i-1] + 1;
    		
    		// 현재의 수가 2로 나누어 떨어지는 경우
    		if(i % 2 == 0)
    			dp[i] = Math.min(dp[i], dp[i/2] + 1);

    		// 현재의 수가 3로 나누어 떨어지는 경우
    		if(i % 3 == 0)
    			dp[i] = Math.min(dp[i], dp[i/3] + 1);
    	}
    	
    	System.out.println(dp[N]);
    	
    }
}