[백준] | JAVA, 자바 | 1463번 - 1로 만들기

https://www.acmicpc.net/problem/1463

---

문제 요약 :

1. 정수 X 입력받기

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

2-1. X가 3으로 나누어 떨어지면, 3으로 나눈다.

2-2. X가 2로 나누어 떨어지면, 2로 나눈다.

2-3. 1을 뺀다.

3. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다.

4. 연산을 사용하는 횟수의 최솟값을 출력

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //1. 정수 X 입력받기
        int n = Integer.parseInt(br.readLine());
        boolean[] visited = new boolean[n + 1];
        Queue<Integer> queue = new ArrayDeque<>();

        queue.add(n);
        visited[n] = true;
        int cnt = 0;
        //2. 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다.
        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                int temp = queue.poll();
                //3. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다.
                if (temp == 1) {
                    System.out.println(cnt);
                    return;
                }
                //2-1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
                if (temp % 3 == 0 && !visited[temp / 3]) {
                    visited[temp / 3] = true;
                    queue.add(temp / 3);
                }
                //2-2. X가 2로 나누어 떨어지면, 2로 나눈다.
                if (temp % 2 == 0 && !visited[temp / 2]) {
                    visited[temp / 2] = true;
                    queue.add(temp / 2);
                }
                //2-3. 1을 뺀다.
                if (temp - 1 >= 1 && !visited[temp - 1]) {
                    visited[temp - 1] = true;
                    queue.add(temp - 1);
                }
            }
            cnt++;
        }
        //4. 연산을 사용하는 횟수의 최솟값을 출력
        System.out.println(cnt);
    }
}