문제

정수 s가 주어진다. 정수 s의 값을 t로 바꾸는 최소 연산 횟수를 구하는 프로그램을 작성하시오.

사용할 수 있는 연산은 아래와 같다.

1. s = s + s; (출력: +)
2. s = s - s; (출력: -)
3. s = s s; (출력: )
4. s = s / s; (출력: /) (s가 0이 아닐때만 사용 가능)

입력

첫째 줄에 s와 t가 주어진다. (1 ≤ s, t ≤ 109)

출력

첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다.

연산의 아스키 코드 순서는 '*', '+', '-', '/' 이다.

예제1 - 입력

7 392

예제1 - 출력

+*+

예제2 - 입력

7 256

예제2 - 출력

/+***

예제3 - 입력

4 256

예제3 - 출력

**

예제4 - 입력

7 7

예제4 - 출력

0

예제5 - 입력

7 9

예제5 - 출력

-1

예제6 - 입력

10 1

예제6 - 출력

/

제출코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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

        long s = Long.parseLong(st.nextToken());
        long t = Long.parseLong(st.nextToken());


        Number now = new Number(s, "");
        Set<Long> check = new HashSet<>();

        Queue<Number> queue = new LinkedList<>();
        check.add(s);
        queue.offer(now);
        while (!queue.isEmpty()) {
            now = queue.poll();
            if (now.val == t) {
                if (now.cal.length() == 0) {
                    System.out.println(0);
                }
                else {
                    System.out.println(now.cal);
                }
                return;
            }
            for (int i = 0; i < 4; i++) {
                long temp = now.val;
                String str = now.cal;
                if (i == 0) {       //*
                    temp = temp * temp;
                    str += '*';
                }
                else if (i == 1) {  //+
                    temp = temp + temp;
                    str += '+';
                }
                else if (i == 2) {  //-
                    temp = 0;
                    str += '-';
                }
                else if (i == 3 && temp != 0) {  ///
                    temp = 1;
                    str += '/';
                }
                else if (i == 3 && temp == 0)
                    continue;

                if (!check.contains(temp)) {
                    queue.offer(new Number(temp, str));
                    check.add(temp);
                }

            }
        }
        System.out.println(-1);
    }
    static class Number {
        public long val;
        public String cal;
        public Number(long val, String cal) {
            this.val = val;
            this.cal = cal;
        }
    }
}