BOJ #1463
https://www.acmicpc.net/problem/1463
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
import java.io.*;
public class B1463 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int d[] = new int[n+1];
d[0] = 0;
d[1] = 0;
for (int i = 2; i <= n; i++){
d[i] = d[i-1] + 1;
if (i % 2 == 0) d[i] = Math.min(d[i], d[i/2] + 1);
if (i % 3 == 0) d[i] = Math.min(d[i], d[i/3] + 1);
}
System.out.println(d[n]);
br.close();
}
}