[코딩 테스트] 1로 만들기 (DP)

문제

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

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

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

입력

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

출력

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

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

3

생각

• 숫자가 커질 수록 연산의 중복이 많아진다 예를 들어 10을 만들기 위해서는 10 -> 9 -> 3 -> 1 이렇게 3번의 연산이 필요한데, 9를 만드는데, 3을 만드는데 이미 연산의 횟수를 계산했었다. 이를 DP를 이용해 중복을 줄여보자!

• 점화식

코드

import java.util.Scanner;

public class MakeOne {
    static int N;
    static int[] dp;

    public int getMinOperationCnt(int N) {

        dp[1] = 0;

        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];
    }

    public static void main(String[] args) {
        MakeOne T = new MakeOne();
        Scanner kb = new Scanner(System.in);

        N = kb.nextInt();
        dp = new int[N + 1];

        System.out.println(T.getMinOperationCnt(N));
        kb.close();
    }
}

생각

• DP 문제 처음 봤을 때는 어려웠는데 확실히 숫자가 커져도 중복 계산을 피하기 위해 이전 계산 결과를 저장하기 때문에 OOM이 덜 발생하는 것 같다.
• 초기화 조건과 점화식만 잘 생각해서 DP로 문제를 풀수 없는지 검토를 해봐야겠다,,!

---

문제 출처