(1463) 1로 만들기

문제

문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

---

문제 풀이

해당 문제는 DP를 활용하여 풀 수 있는 문제이다. 문제에서 주어졌듯이 현재 값에 -1 또는 ÷ 2 또는 ÷ 3을 하여 최적해로 1을 만들 수 있는 경우의 수를 만들어야 한다는 문제이다. 

 

첫번째에 dp값을 초기화 해줄 때,  dp[0] ~ dp[1] 까지 0으로 초기화 해둔 상태로 시작해도 무방하다. 그리고 2부터는 dp [i -1값에 다가 + 1 을 해준 값을 입력을 해주면 되는데 그러한 이유는 현재 인덱스 값에서 이전 인덱스의 경우의 수는 1개이기 때문이다. 

 

 아래 사진을 보고 다시 설명 하자면, 초기 dp 배열 값들 중 index 0 ~ 1은 0으로 초기화를 시켜둔다.

값이 2와 3일 때는 ÷2 와 ÷3으로 한번에 값을 1로 만들수 있기 때문에 dp[i / 2] + 1 또는 dp[i / 3] + 1 방식으로 배열의 값을 채워준다. 

4의경우도 ÷ 2를 통해 한번에 원하는 값을 만들 수 있다. 하지만 5의 경우는 다르다. 먼저 -1을 하여 4를 만든 다음에 ÷ 2를 해야 하는데 이러한 경우 조건이 dp[i -1] + 1 값이 되어져야 한다는 것이다. 즉 dp[4] = 2 였으므로, d[5] = 3이 된다. 

6과 7도 같은 방식으로 채우게 되면 6은 ÷ 3 으로 2 값이 들어가고 7은 2 + 1값이 들어 가게 된다.  

---

나의 답안

private static int solution(int n) {
    int[] dp = new int[n + 1];

    for (int i = 2; i <= n; 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);
        }
    }

    return dp[n];
}