1463번
문제
- 정수 N에 사용할 수 있는 연산은 아래의 세 가지
- N이 3으로 나눠 떨어지면, 3으로 나눈다.
- N이 2로 나눠 떨어지면, 2로 나눈다.
- 1을 뺀다.
- 정수 N이 주어졌을 때 위의 3가지 연산을 적절히 사용해서 1을 만들 때, 연산을 사용하는 횟수의 최소값을 구하는 문제
문제 해결 순서
- N+1만큼 크기의 배열 arr을 선언하고 99999999로 초기화
- 배열의 순번 I가 곧 I를 1로 만들기 위해 사용하는 연산 횟수의 최소값
- 1은 연산을 할 필요가 없으므로 0으로 초기화
- 2부터는 1) 2로 나눴을 때 기존의 arr[i]와 arr[i/2]+1 중 더 작은 값을 arr[i]로 초기화
2) 3로 나눴을 때 기존의 arr[i]와 arr[i/3]+1 중 더 작은 값을 arr[i]로 초기화
3) 1을 뺐을 때 기존의 arr[i]와 arr[i-1]+1 중 더 작은 값을 arr[i]로 초기화
5. 숫자를 점점 키워 나가면 이미 구해진 이전의 i번째 최소값으로 원하는 N번째의 최소값을 구할 수 있음
ex) i가 10일때, i/2인 5의 최소값이 3이란 걸 이미 알고 있고, i-1인 9의 최소값이 2란 걸 이미 알고 있기 때문에 9의 최소값 + 1인 3이 10의 최소값이 됨
6. 위와 같은 방법이 다이나믹 프로그래밍을 풀기위한 Botton-Up 방식, 밑에서부터 원하는 값을 구해 점점 키워나간다는 뜻
```java
import java.util.Arrays;
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n+1];
Arrays.fill(arr,99999999);
arr[1] = 0;
for(int i=2;i<=n;i++){
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);
arr[i] = Math.min(arr[i],arr[i-1]+1);
}
System.out.println(arr[n]);
}
}
```
