백준 1463 1로 만들기 java 풀이

문제

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

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

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

입력

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

출력

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

 

나의 풀이

 풀이 접근은 최종값은 항상 1이기 때문에 1부터 시작해서 주어진 수 num 까지 올라가는 bottom-up 방식으로 풀이를 시작했다. (그냥 풀었는데 정리하면서 찾아보니 bottom-up이라는 용어가 있었음...)

 DP니깐 이전 연산은 저장해놔야한다 라는 개념이 있다보니 어떻게 값을 저장할지가 고민이었다. 그러다 찾은 방법이 배열을 만들고 arr[n]에는  1 을  세 가지 연산 +1, *2 , *3 을 조합해 n을 만들때까지 필요한 최소한의 연산 횟수를 저장해 나가는 방법이었다.

 

 쉽게 예시로 보자면

    arr[2] 는 1를 2로 만들기 위해 +1, *2, *3  세 가지 연산을 사용하면서 연산 횟수가 가장 적은 값을 저장한다.

    arr[3] 은 1을 3로 만들기 위해 +1, *2, *3 세 가지 연산을 사용하면서 연산 횟수가 가장 적은 값을 저장한다.

 

 이와 같은데 여기서 DP의 개념을 적용할 수 있는 부분이 바로 1을 n/3까지 도달하게 할때 최소연산횟수를 x라 하면

 1-> n 까지 필요한 최소 연산횟수는 x + 1 이라는 점이다. 

 

 쉽게 예시로 보자면

  1 -> 3으로 만들기 위한 연산은 최소 1회 (*3 연산시)

  1 -> 9 로 만들기 위한 연산은 1+1 = 2회 라는 점 (*3 연산시)

 

 이를 +1 연산이나 *2 연산에도 적용해 점화식으로 보자면

   arr[n] = arr[n-1] +1  

   arr[n] = arr[n/2] +1  (n%2==0)

   arr[n] = arr[n/3] +1   (n%3==0)

 

여기 까지만 봐도 이제 배열의 규칙성이 보이기 시작하는데, 만약 n이 2와 3 모두 나누어 떨어지는 수라면 위 세 가지 연산 결과 중 가장 값을 arr[n] 에 대입해주면 되는 것이다. 

 

 

코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int num = Integer.parseInt(br.readLine());
        int[] arr = new int[num+1];
        
        for(int i=2; i<=num; i++) {
            arr[i] = arr[i-1]+1;
            if(i%2==0)
                arr[i] = Math.min(arr[i], arr[i/2]+1);
            if(i%3==0)
                arr[i] = Math.min(arr[i], arr[i/3]+1);
        }
        
        bw.write(arr[num]+"\n");
        bw.flush();
    }
}