DP - 1로 만들기

DP(Dynamic Programming) 기법
해결한 부분 문제의 정답을 메모리에 기록하여, 한 번 계산한 답은 다시 계산하지 않도록 하는 캐싱 기법을 활용하여 문제의 시간 복잡도를 줄이는 문제 해결 기법. -> 탑다운(재귀함수),바텀업(반복문) 활용 가능

✅ 문제

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.

X가 5로 나누어떨어지면, 5로 나눈다.
X가 3으로 나누어떨어지면, 3으로 나눈다.
X가 2로 나누어떨어지면, 2로 나눈다.
X에서 1을 뺀다.
정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력 예시
26

출력 예시
3

💻 코드

import java.util.*;

public class DP_Exercise2
{
    static int[] dp = new int[30001];

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = 0;
        try
        {
            n = sc.nextInt();
            if(n > 30000)
            {
                Exception ex = new Exception("입력 값이 30000 초과");
                throw ex;
            }
        }
        catch (Exception e)
        {
            System.out.println(e.getMessage() + ", 프로그램을 재실행하시오.");
        }
        for(int i = 2; i < n + 1; 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이 나올 경우 결과를 리턴하는 함수를 재귀함수로 구현하고자 하였고, 이에 따라 HashMap을 이용해서 key 값으로 그 입력 받은 숫자값과 value 값으로 계산 수행 순번은 count++해서 구현하고자 하였으나.. 해당 함수에 대해 익숙치 않은 탓 + 너무 복잡해지는 계산으로 인해 풀이를 보고 깨달음을 얻었다..
점화식을 직접적으로 생각하지 않았으나 이를 함수로 구현하는 과정이 머릿속에 아직 정립되지 않는 걸로 보아 연습이 많이 필요할 것 같아 보인다.