[백준 1463번] 1로 만들기

문제

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

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.
   정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

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

출력

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

---

정답

처음에는 큰수로 나누는게 가장 1에 빨리 도달할것이라고 생각하였다. 근데 아닌 경우가 생겼다.
10에서 예외 케이스가 발생했다.
10/2 => 5-1 => 4/2 => 2/2 => 1 로 4번으로 구할 수도 있지만
10-1 => 9/3 => 3/3 => 1 로 3번 만에 구할수 있다.

이 문제는 다이나믹 프로그래밍 문제이다.

• top-down 은 재귀를 이용한 방법이고
• bottom-up 은 반복문을 이용하는 방법이다.
  둘다 공통적으로 D[] 라는 배열을 만들어서 그 곳에 계산결과를 저장해 다른 문제를 해결할때 활용하는 방법이다

0 과 1은 1까지 변환할 필요가 없으니 횟수가 0 이다.

0	1	2	3	4	5	6	7	8	9
0	0

2에 가능한 계산 방법은 -1 또는 /2 뿐이다. 비교를 해보자

• 2-1 = 1 이다. 결국 2가 1이 되는 횟수는 1 이 1이 되는 횟수 +1 한 값과 똑같다.
• 2/2 = 1 이다. 결국 2가 1이 되는 횟수는 1 이 1이 되는 횟수 +1 한 값과 똑같다.
• 2 /3 = 0 이다. 계산을 못한다.
  위의 순서를 코드로 정리하면
• d[2] = d[2-1] + 1; if(2 % 2 == 0) d[2] = Math(d[2/2]+1, d[2]); //위에서 D배열에 현재 숫자의 횟수와 2로 나눴을때의 횟수를 비교해서 더 작은 값을 D배열에 넣는다.

0	1	2	3	4	5	6	7	8	9
0	0	1

3에 가능한 계산 방법은 -1 또는 /3 뿐이다. 비교를 해보자

• 3-1 = 2 이다. 결국 3이 1이 되는 횟수는 2가 1이 되는 횟수 +1 한 값과 똑같다.
• 3/3 = 1이다. 결국 3이 1이 되는 횟수는 1이 1이 되는 횟수 +1 한 값과 똑같다.
• 3/2 는 계산을 못한다.
  위의 순서를 코드로 정리하면위 와 같은 순서대로 작은 문제의 정답을 기록해가면서 큰 문제를 푸는것이 다이나믹 프로그래밍 방법이다.
  아래는 반복분으로 푼 방법이다.

d[3] = d[3-1]+1; if(3 % 3 == 0) d[3] = Math.min(d[3 / 3] +1 , d[3] ); //d[3/3] = d[1] = 0 +1 < d[3-1] = 2 => 1<2이므로 3으로 나누는 방법이 더 횟수가 작다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int number = scan.nextInt();

        int dp[] = new int[number+1];
        dp[0] = 0;
        dp[1] = 0;
        for(int i=2; i<=number; 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[number]);
    }
}

1463번