[백준] 1463번 : 1로 만들기 (JAVA)

1. 문제 분석

 

이 문제는 바로 전날 풀었던 1149번 RGB거리와 매우 유사하다. 정수 X를 1로 만드는 최소 횟수를 구하면 된다. 작은 문제에서 큰 문제로 해결해가는 Bottom-Up 방식으로 풀면 될거 같았다. 

시간복잡도 : O(N) 

알고리즘 : DP

2. 문제 풀이

2~X까지 각 숫자가 1이 되는 최솟값을 구하면 된다. 작은 값부터 배열에 저장해가면서 최종 값을 계산한다.

• dp[i] = dp[i-1] + 1 
• dp[i] = dp[i/2] + 1 (단 i가 2로 나누어질 때)
• dp[i] = dp[i/3] + 1 (단 i가 3로 나누어질 때)

3. 코드 구현

import java.util.Scanner;

public class BOJ_1463 {


    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int X = sc.nextInt();
        sc.close();

        int[] dp = new int[X + 1];

        for(int i = 2; i <= X; i++){
            dp[i] = dp[i-1]+1;

            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[X]);
    }
}