[白俊]#143954演算

質問する

整数sを与えます.整数sの値をtに変換する最小演算回数を求めるプログラムを作成する.
使用可能な演算は次のとおりです.

s = s + s; (出力:+)

s = s - s; (出力:-)

s = s s; (出力:)

s = s/s; (出力:/)(sが0でない場合のみ使用可能)

入力

最初の行はsとtを与える.(1≤s,t≤109)(1 ≤ s, t ≤ 10^9)(1≤s,t≤109)

しゅつりょく

1行目に整数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

入力例5

10 1

サンプル出力5

/

に答える

この問題はbfs(幅優先探索)アルゴリズムで容易に解決できる.最大値は10910^9109なので、HashSetを使用してチェックを繰り返します.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int start = Integer.parseInt(input[0]);
        int target = Integer.parseInt(input[1]);

        if(start==target) {         //타겟 값과 같은 경우
            System.out.println(0);
            return;
        }

        bfs(start, target);
    }

    public static void bfs(int start, long target) {
        Queue<Pair> queue = new LinkedList<>();
        HashSet<Integer> set = new HashSet<>();
        int min_len = Integer.MAX_VALUE;
        String ans = "";
        set.add(start);
        queue.add(new Pair(start, ""));

        while(!queue.isEmpty()) {
            Pair temp = queue.poll();

            if(temp.num==target) {        //타겟 값에 도달한 경우 최소값 유효성 체크
                if(min_len>=temp.str.length()) {
                    if(min_len==temp.str.length()) {
                        ans = ans.compareTo(temp.str) < 0 ? ans : temp.str;
                    }

                    else {
                        min_len = temp.str.length();
                        ans = temp.str;
                    }
                }
            }

            if(!set.contains(0)) {        //'-'는 무조건 0 이기 때문에 처음에 먼저 계산
                set.add(0);
                queue.add(new Pair(0, "-"));
            }

            if(!set.contains(1)) {      //'/'는 무조건 1 이기 때문에 마찬가지로 먼저 계산
                set.add(1);
                queue.add(new Pair(1, "/"));
            }

            if((long)temp.num*temp.num<=target && !set.contains(temp.num*temp.num)) {       //'*'가 가능한 경우, '*'가 '+'보다 아스키 코드 값이 작기 때문에 먼저 체크
                if(temp.num*temp.num==target)
                    queue.add(new Pair(temp.num*temp.num, temp.str+"*"));

                else {
                    set.add(temp.num*temp.num);
                    queue.add(new Pair(temp.num*temp.num, temp.str+"*"));
                }
            }

            if((long)temp.num+temp.num<=target && !set.contains(temp.num+temp.num)) {     //'+'가 가능한 경우
                if(temp.num+temp.num==target)
                    queue.add(new Pair(temp.num+temp.num, temp.str+"+"));

                else {
                    set.add(temp.num+temp.num);
                    queue.add(new Pair(temp.num+temp.num, temp.str+"+"));
                }
            }
        }

        if(ans.equals(""))          //도달 불가능한 경우
            System.out.println(-1);
        else
            System.out.println(ans);
    }

    public static class Pair {
        int num;
        String str;

        public Pair(int num, String str) {
            this.num = num;
            this.str = str;
        }
    }
}