[백준-1463]-[다이나믹프로그래밍]-1로 만들기

문제 링크 

https://www.acmicpc.net/problem/1463

DP 문제에서 중요한 점화식을 구해보고자 2부터 1이 되는 경우를 5정도까지 구해보았다.

2 같은 경우 

{

2 - 1,  

2 / 2 

}  정도가 있고 최소 횟수는 1 이다. 

3 같은 경우 

{ 

3 -1 -1 , 3 / 2} 가 있고 2로는 나눌수 없기 때문에 최소 횟수는 1 이다.

4 같은 경우 { 4 -1 -1 -1 , 4 / 2  /2 ,  4 -1 / 3 ) 등을 생각 할 수 있고 최소 횟수는 2 가 된다.

5 같은 경우 { 5 -1 -1 -1 -1,  5 -1  2/ 2 , 5 -1 / -1/ 3) 등을 생각할 수 있으며 최소 횟수는 3이 된다.

어느정도 공통점이 보이는거 같다. 

2와 3은 일단 넘어가고 4와 5를 보자면

4에서 1을 빼면 3

4에서 2를 나누면 2

4에서 3을 뺄 순 없으니깐 제외 

4의 경우의 수는 3에서 1 만드는 경우의 수와 2에서 1만드는 경우의수 에 1 더한 값이 된다는게 보인다.

2랑도 나눠지고 3으로도 나눠지는 6으로 다시한번 확인해보자.

6에서 1을 뺀 값은 5, 그럼 [5]의 최소 횟수에 1을 더하면 -1을 한 경우의 최소 횟수를 알 수 있다. 

5의 최소 횟수는 3이니깐 -1 한 경우의 최소횟수는 4가 된다.

6에서 2를 나눈 값은 3 이고 [3] 의 최소 횟수는 1 [3]의 최소횟수에 1을 더한 횟수가 6에서 2를 나눈 값의 최소횟수다.

6에서 3을 나눈 값은 2 이고 [2] 의 최소 횟수는 1 [2]의 최소횟수에 1을 더한 횟수가 6에서 3을 나눈 값의 최소횟수다.

여기서 1을 뺀 경우, 2를 나눈 경우, 3을 나눈경우의 최소 횟수가 6에서 1을 만들때의 최소 횟수가 된다. 

그럼 6에서 1을 만드는 최소 횟수는 2가 된다. 

공통적인 부분을 찾았고 점화식은 F(X) = F(X-1) +1 또는 F(X/2) +1 또는 F(X/3) +1 이 될거 같다. 

1에서 부터 입력받은 숫자 X까지 재귀로 하나하나 계산해 나가면 원하는 값을 구할 수 있다.

소스

import java.util.Scanner;
 
public class E_1463 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int NUM = sc.nextInt();
        
        int[] arr = new int[NUM+1];
        
        arr[0] = 0;
        
        for(int i=2; i <= NUM; i++) {
            // -1 한 경우의 최소 횟수
            arr[i] = arr[i-1] +1;
 
            
            if(i%2 == 0) {
                arr[i] = (arr[i/2] + 1 < arr[i])?arr[i/2] + 1:arr[i];
            }
            
            if(i%3 == 0) {
                arr[i] = ( arr[i/3] + 1 < arr[i] ) ? arr[i/3] + 1: arr[i];
            }
        }
        System.out.println(arr[NUM]);
    }
}