[백준 알고리즘] 1463번 : 1로 만들기

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

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

출력

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

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_1463 {
    static Integer[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        dp = new Integer[N + 1];
        dp[0] = dp[1] = 0;

        System.out.println(recur(N));
    }

    public static int recur(int N) {
        if (dp[N] == null) {
            if (N % 6 == 0) {
                dp[N] = Math.min(recur(N - 1), Math.min(recur(N / 3), recur(N / 2))) + 1;
            } else if (N % 3 == 0) {
                dp[N] = Math.min(recur(N / 3), recur(N - 1)) + 1;
            } else if (N % 2 == 0) {
                dp[N] = Math.min(recur(N / 2), recur(N - 1)) + 1;
            } else {
                dp[N] = recur(N - 1) + 1;
            }
        }
        return dp[N];
    }
}

풀이 및 느낀점

어떤 수를 1로 만들어야하는 문제였다. dp로 문제에 접근하였다. 3가지 방법으로 1을 만들 수 있는데, 3으로 나누는 방법과 2로 나누는 방법, 마지막으로 1로 빼주는 방법이 있다. 처음에는 3으로 나뉘는 경우, 2로 나뉘는 경우, 1로 빼주는 경우만 생각했는데 3과 2 모두 나뉘는 경우도 생각해줘야했다. 그래서 6으로 나뉘는 경우까지 포함하여, 총 4가지의 방법으로 조건문을 이용하여 표현했다. 각각의 조건문 식에서 1을 더해준 이유는 직전까지 구한 방법 수에 현재 방법 수까지 더해주기 위함이다.

참고자료