정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int MAX = 1000000;
public static int BFS(int start_point, int last_point) {
boolean[] visited = new boolean[MAX + 1];
int[] map = new int[MAX + 1];
int count=0;
map[start_point] = count;
Queue<Integer> will_visit = new LinkedList<Integer>();
will_visit.add(start_point);
visited[start_point]=true;
int num=0;
while (will_visit.size() > 0) {
int current_point = will_visit.remove();
if (current_point == last_point)
return map[current_point];
if (current_point < 0 || current_point > MAX)
continue;
if(current_point%3==0 && !visited[current_point/3])
{
num = current_point/3;
will_visit.add(num);
map[num] = map[current_point]+1;
visited[num] = true;
}
if(current_point%2==0&& !visited[current_point/2])
{
num = current_point/2;
will_visit.add(num);
map[num] = map[current_point]+1;
visited[num] = true;
}
if(!visited[current_point-1])
{
will_visit.add(current_point-1);
map[current_point-1] = map[current_point]+1;
visited[current_point-1] = true;
}
}
return 0;
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(reader.readLine());
System.out.println(BFS(num, 1));
}
}