[JAVA] 백준 1463번 【1로 만들기】

---

Dynamic Programing을 사용하는 문제이다.

 

먼저, 메모이제이션 해둘 dp[ ] 배열을 생성한다.

 

dp[n]의 의미는 n에서 1로 변환할때 드는 최소의 연산수를 저장할 것이다.

 

먼저 dp[0] 과 dp[1] 의 값이 0 임은 명확한 사실이고, dp[2]부터 조건문을 이용해 정의를 한다.

---

2를 1로 만드는 횟수의 최솟값은 무엇일까.

 

먼저 2가지 연산을 진행할 수 있다. 1을 빼거나, 2를 나누는 것

 

2-1 = 1 이므로 dp[2]=dp[1]+1=0+1=1

 

2/2=1 역시, dp[2]=dp[1]+1=0+1=1이다.

 

둘다 값이 1이므로 두 연산의 최솟값은 1이다.

 

2에서 1로 만드는 연산의 최솟값은 1이므로, dp[2]=1을 기록한다.

---

3을 1로 만드는 횟수의 최솟값은?

 

3은 1을 빼거나 3을 나누는 것 두가지 연산을 수행할 수 있다.

 

3-1은 2가 되고 2에서 1로 만드는 최소 연산수는 윗 과정을 통해 이미 1인것을 알고 있으므로

 

dp[3]=dp[2]+1=1+1=2가 된다.

 

3으로 나누는 연산을 수행하면 3/3= 1이 되고

 

dp[3]=dp[1]+1=0+1=1이 된다.

 

즉, 두 연산을 비교해봤을때, 3으로 나누는 경우가 2보다 작은 1인 경우가 존재하므로 dp[3]=1을 기록한다.

---

4를 1로 만드는 횟수의 최솟값은?

 

4는 1을 빼거나 2로 나누는 두가지 연산을 수행할 수 있다.

 

4-1=3이 되고 3에서 1로 만드는 최소의 횟수는 dp[3]=1이므로 dp[4]=dp[3]+1=1+1=2가 된다.

 

4/2=2가 되므로 2에서 1로 만드는 최소의 횟수는 dp[2]=1이므로, dp[4]=dp[2]+1=1+1=2가 된다.

 

둘다 2번의 횟수가 소요되기 때문에 dp[4]=2가 된다.

---

6의 경우에는, dp[5](1을 뺀 경우) 와 dp[3] (2로 나눈 경우) 과 dp[2] (3으로 나눈 경우) 를 비교하여 이 세가지 값 중 최솟값에 1을 더한 값이 dp[6]이 될 것이다.

 

이런 방법으로 입력받은 X까지 연산을 수행하여 dp를 채우는 것이다.

 

X 값 미만으로 dp값을 다 채워놨기 때문에, dp[X-1] 과 dp[X/3] 과 dp[X/2]를 비교하여 그 중 작은 값에 +1 한 값이 최소의 연산 횟수가 될 것이다.

 

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int X = scanner.nextInt();
        int [] dp = new int[X+1];
        dp[0]=0;
        dp[1]=0;

        for(int i=2;i<=X;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);
        }
        System.out.println(dp[X]);
    }
}