Baekjoon #14395

Baekjoon #14395

1개의 풀이 · Java

문제 원문 보기 ↗

SOLUTION INFO

Java · Main.java

Main.java
import java.util.*;
import java.io.*;

public class Main {
    private static long s, t;

    public static void main(String[] args) {
        FastReader rd = new FastReader();

        s = rd.nextLong();
        t = rd.nextLong();

        if (s == t) {
            System.out.println(0);
            return;
        }

        Queue<Node> q = new LinkedList<>();
        HashSet<Long> h_set = new HashSet<>();
        q.add(new Node(s * s, "*"));
        h_set.add(s * s);
        q.add(new Node(s + s, "+"));
        h_set.add(s + s);
        q.add(new Node(1L, "/"));
        h_set.add(1L);


        boolean check = false;
        while (!q.isEmpty()) {
            Node curr = q.poll();
            if (curr.num == t) {
                System.out.println(curr.str);
                check = true;
                q.clear();
                break;
            }

            if (curr.num > 1e9) continue;

            long num = curr.num;
            if (!h_set.contains(num * num)) {
                h_set.add(num * num);
                q.add(new Node(num * num, curr.str + "*"));
            }

            if (!h_set.contains(num + num)) {
                h_set.add(num + num);
                q.add(new Node(num + num, curr.str + "+"));
            }


        }

        if (!check) System.out.println(-1);
    }


    static class Node {
        long num;
        String str;

        Node(long num, String str) {
            this.num = num;
            this.str = str;
        }

    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

SOLUTION DESCRIPTION

풀이 설명

1. BFS 응용문제. 문제에 대한 이해도가 어느정도 필요한 문제이다. 2. 단순히 4연산을 모두 반영하여 문제를 해결하는 방법도 있으나, 사실 2연산 탐색을 추구하여도 충분히 문제를 풀 수 있는 문제이다. `-` , `/` 의 경우 어떤 `s`값이라 할지라도 `0` , `1` 이 반환된다. 즉, 임의의 탐색을 진행하는 도중에 `-`, `/` 를 사용하는 것보다 맨 처음연산에 `-` , `/` 을 반영하는 경우가 더욱 연산횟수가 적을 수 밖에 없다. 3. 더불어, `s,t` 의 입력값의 범위는 `1 <= s,t <= 1e9` 이므로 사실상 `-` 연산은 출력값에 절대 반영될 수 없다. 4. 따라서, 이 문제는 첫 연산에서만 `*,+,/` 연산을 반영하고, 나머지 탐색 연산에서는 `*,+` 만 사용하는 것으로도 정답을 도출할 수 있다. 5. 이외에 해당 문제에서 조심해야할 부분들을 다음과 같다. a. 재방문 처리를 진행하기 위해서 배열을 사용할 수 없다. 입력 범위가 너무 크기 때문이다. `Set` 이나 `Map` 을 활용하여 해결하자. b. `*,+` 연산 시 `int` 범위를 넘어갈 수 있다.