[BOJ] 백준 1463 - 1로 만들기 풀이

1. 문제

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

1463번: 1로 만들기

 

2. 풀이

백준 실버 3의 DP 문제이다. 정말 DP는 풀어도 풀어도 해결할 방법이 보이지 않는 것 같다..

우선 이 문제를 보고 N이 주어졌을 때, (1), (2), (3)의 상황에 맞게 if문을 걸고 재귀를 타면서 문제를 풀었지만, 시간초과가 발생했다.(문제의 시간 제한이 0.15초이기도 했고 N이 최대 10^6이기도 했으니 어마어마한 시간이 걸렸을 것이다.)

해결점은 DP에서 찾을 수 있었다.
우선 DP 배열을 정의할 때 dp[i] = p;  // 인덱스(i)를 1로 만들기 위한 최소의 연산횟수로 잡았다.
그 후 dp[0]과 dp[1]에 0을 대입한다. 이유는 N이 1보다 크거나 같다고 했고, 정답이 주어진 수를 1로 만드는 최소 횟수이기 때문에 1은 자연스럽게 답이 0이 된다.

이제 for문을 돌면서 메모이제이션해주면 된다.
우선 (전 인덱스의 dp값 + 1)을 현 인덱스의 dp값에 넣어준 후 분기를 나누어 각각 계산한다.
1. 2로 나누었을 때의 나머지가 0일 때.
2. 3으로 나누었을 때의 나머지가 0일 때.

계산할 때는 i를 1로 만들기 위한 최소 연산 횟수이므로 1일 때는 i / 2를, 2일 때는 i / 3을 해준다.
예를 들어 dp[12]의 경우 2로 나누어 떨어지기도 하며, 3으로 나누어 떨어지기도 하기 때문에 각각 if를 걸어 확인해주어야 한다.
(ex: 2일 경우 :  dp[12] ==> dp[6] + 1, 3일 경우 : dp[12] ==> dp[4] + 1)

마지막으로 dp의 N번째(이는 N을 각 연산을 해주었을 때 1이 되는 최소 연산 횟수를 의미)를 출력해주면 정답!!!

 

3. 소스 코드

(1) 시간 초과 코드(재귀)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    static int result = Integer.MAX_VALUE;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        if (N % 3 == 0) {
            DivisionThree(N, 0);
        }

        if (N % 2 == 0) {
            DivisionTwo(N, 0);
        }

        MinusOne(N, 0);

        bw.write(Integer.toString(result));
        bw.flush();
        bw.close();
        br.close();
    }

    public static void DivisionThree(int x, int cnt) {
        if (x == 1) {
            result = Math.min(cnt, result);
        } else if (x < 1) {
            return;
        } else {
            x /= 3;
            cnt += 1;

            if (x % 3 == 0) {
                DivisionThree(x, cnt);
            }
            if (x % 2 == 0) {
                DivisionTwo(x, cnt);
            }
            MinusOne(x, cnt);
        }
    }

    public static void DivisionTwo(int x, int cnt) {
        if (x == 1) {
            result = Math.min(cnt, result);
        } else if (x < 1) {
            return;
        } else {
            x /= 2;
            cnt += 1;

            if (x % 3 == 0) {
                DivisionThree(x, cnt);
            }
            if (x % 2 == 0) {
                DivisionTwo(x, cnt);
            }
            MinusOne(x, cnt);
        }
    }

    public static void MinusOne(int x, int cnt) {
        if (x == 1) {
            result = Math.min(cnt, result);
        } else if (x < 1) {
            return;
        } else {
            x -= 1;
            cnt += 1;

            if (x % 3 == 0) {
                DivisionThree(x, cnt);
            }
            if (x % 2 == 0) {
                DivisionTwo(x, cnt);
            }
            MinusOne(x, cnt);
        }
    }
}

(2) 정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    static int[] dp;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        dp = new int[N + 1];
        dp[0] = 0;  // 인덱스를 1로 만들기 위한 최소의 연산횟수
        dp[1] = 0;

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

            // 3으로 나누어 떨어질 때
            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i / 3] + 1, dp[i]);
            }

            // 2로 나누어 떨어질 때
            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i / 2] + 1, dp[i]);
            }
        }

        bw.write(Integer.toString(dp[N]));
        bw.flush();
        bw.close();
        br.close();
    }
}