DP - 1로 만들기

문제

이것이 취업을 위한 코딩테스트다 with 파이썬 (https://youtu.be/5Lu34WIx2Us)

• 정수 X에 사용할 수 있는 연산
  • X가 5로 나누어 떨어지면, 5로 나누기
  • X가 3으로 나누어 떨어지면, 3으로 나누기
  • X가 2로 나누어 떨어지면, 2로 나누기
  • X에서 1빼기
• 정수 X가 주어졌을 때, 연산 4개를 적절히 사용하여 값을 1로 만든다.
  이때 연산을 사용하는 횟수의 최솟값을 출력하라.

 

입력 조건

• 첫째 줄에 정수 X가 주어진다. (1 <= X <= 30,000)

 

출력조건

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

 

풀이

• 최적 부분 구조와 중보되는 부분 문제를 만족하기 때문에 DP 풀이
• f(i) = i를 1로 만들기 위한 최소 연산 횟수
• 예를 들어 X가 6이면,
  각각 처음 연산이 -1일 경우, /3일 경우, /2일 경우 세 가지 경우의 수를 전부 구한다.
  이때 각각의 연산에서 값들이 점점 작아질 텐데, 연산에 필요한 값들이 이미 계산된 적 있는지 체크한 뒤 메모 리스트에서 해당 값을 가져오면 연산 시간을 줄일 수 있다.
• X가 6이고 처음 연산이 -1일 경우의 필요한 연산 횟수는 = (X가 5일 경우 1이 되기 위한 최소 연산 횟수 + 1)이다.
  +1을 하는 이유는 위에서 처음 연산 -1을 연산 개수에 포함시킨 것.
• X가 6일 경우 최소 연산 횟수
  = (-1을 할 경우(5) 최소 연산 횟수, /3을 할 경우 최소 연산 횟수(2), /2를 할 경우(3) 최소 연산 횟수) 중 최솟값 + 1
• -1 빼기 / 2로 나누기 / 3으로 나누기 / 5로 나누기 각 경우와 현재 최소 연산 횟수(DP테이블)를 비교해서 둘 중 작은 값을 최소 연산 횟수로 저장

 

코드

import java.util.Scanner;

// 1로 만드는 최소 연산 횟수 구하기
public class Main {
    // 앞서 계산된 결과 저장용 DP 테이블 (index 값을 1로 만드는 최소 연산 횟수)
    public static int[] d = new int[30001];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();

        // DP Bottom-Up
        for (int i = 2; i <= x; i++) {
            // 1을 빼는 경우
            d[i] = d[i-1] + 1;

            // 2로 나누어 떨어지는 경우
            if (i % 2 == 0)
                d[i] = Math.min(d[i], d[i / 2] + 1);

            // 3으로 나누어 떨어지는 경우
            if (i % 3 == 0)
                d[i] = Math.min(d[i], d[i / 3] + 1);
            
            // 5로 나누어 떨어지는 경우
            if (i % 5 == 0)
                d[i] = Math.min(d[i], d[i / 5] + 1);
        }

        System.out.println(d[x]);
    }
}