[이코테] 1로 만들기, DP

문제 풀이

해당 문제는 dp를 통해 쉽게 구할 수 있다.

30를 1로 만드는 경우의 수를 생각해보자
30은 주어진 a b c d 연산을 모두 수행할 수 있다.
즉, 다음 4과정에서의 최솟 값을 구하는 것과 같다.

A: 30 = 29를 1로 만드는 연산 횟수 + 1 (+1을 하는 연산)
B: 30 = 6을 1로 만드는 연산 횟수 + 1 (*5를 하는 연산)
C: 30 = 10을 1로 만드는 연산 횟수 + 1 (*3을 하는 연산)
D: 30 = 15를 1로 만드는 연산 횟수 + 1 (*2를 하는 연산)

이를 수식으로 표현하면 min(A, B, C, D)+1 과 같이 나온다.

그럼 여기서 B가 선택되었다고 가정해보자.
B에서 6을 을 1로 만드는 연산 횟수는 어떻게 구할까?
똑같이 6을 +1, *5, *3, *2를 했을 때 최솟값을 구하는 것이다.
이제 DP를 활용해야 한다는 것을 이해했을 것이다.
바로 코드를 살펴보자

코드

package 이코테.기출분석.DP;

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

public class _1로만들기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] dp = new int[n+1];
        Arrays.fill(dp, 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);
            }
            if (i % 5 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 5] + 1);
            }
        }

        System.out.println(dp[n]);
    }
}

우선 이전 값에서 +1을 연산한 결과값을 넣어두고
각 연산에 해당하는 배수라면 이전 나눠지는 값에서 곱했을 때와 +1을 했을 때의 값이랑 비교하여 작은 값을 선택하여 지정한다