[Algorithm] 1로 만들기

문제

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

a. X가 5로 나누어 떨어지면 5로 나눈다.

b. X가 3으로 나누어 떨어지면 3으로 나눈다.

c. X가 2로 나누어 떨어지면 2로 나눈다.

d. X에서 1을 뺀다.

 

정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만드려고 한다.

연산을 사용하는 횟수의 최소값을 출력하시오.

 

예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최소값이다.

1. 26 - 1 = 25 (d)

2. 25 / 5 = 5 (a)

3. 5 / 5 = 1 (a)

 

입력 조건

첫째 줄에 정수 X가 주어진다.

 

출력 조건

연산을 하는 횟수의 최소값을 출력한다.

 

풀이

a와 d 조건만 있다면, a가 먼저 가능한지 확인하고 안되면 d를 진행하는 방식으로 진행했을테지만

위와 같은 경우는 a가 안되서 b, c를 먼저할 경우 최소값을 구할 수 없다.

(예시와 같이 d를 진행해야 최소가 되는 경우가 있음)

 

다이나믹 프로그래밍을 이용한다. 바텀업 방식으로 배열에 1이 되는데 필요한 횟수를 저장한다.

import java.util.*;

class Main {

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

    int[] d = new int[30001];
    
    for (int i = 2; i <= x; i++) {
      d[i] = d[i - 1] + 1; // 1을 더할 경우
      if (i % 2 == 0) // 2로 나눠질 경우
        d[i] = Math.min(d[i], d[i/2] + 1);
      if (i % 3 == 0) // 3으로 나눠질 경우
        d[i] = Math.min(d[i], d[i/3] + 1);
      if (i % 5 == 0) // 5로 나눠질 경우
        d[i] = Math.min(d[i], d[i/5] + 1);
    }

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

  } // end main
}

바텀 업 방식으로 1의 경우 연산이 필요 없이 0이고, 2의 경우 -1 연산을 통해 1번의 연산이 필요하고,

3의 경우 3으로 나누는 1번의 연산이 필요하다.

 

경우의 수를 따져보면, 각 경우의 수에서 가능한 경우의 최소 값을 구하면 된다.

 

12라는 숫자의 경우 1을 뺄 수 있고, 2로 나눌 수 있고, 3으로도 나눌 수 있다.

11 (12-1)까지의 연산 + 1 (d[11] + 1)과,

6 (12/2)까지 연산 + 1 (d[6] + 1),

4 (12/3)까지 연산 + 1 (d[4] + 1)의 비교를 통해 최소값이 연산 횟수의 최소값이 된다.

 

d[11], d[6], d[4]는 이미 앞선 연산에서 결과가 나와있기 때문에 빠르게 값을 가져와 연산할 수 있다.

 

x = 26인 경우,

1을 빼거나, 2로 나누거나 선택할 수 있다.

d[25]와 d[13]의 비교를 통해 더 작은 값인 d[25]+1을 선택하게 된다.