백준 17394 자바 - 핑거 스냅 (BOJ 17394 JAVA)

문제 : https://www.acmicpc.net/problem/17394

 

  일단 A와 B 사이의 소수라는 조건이 없다고 생각해보자.

이 경우 1차원 좌표평면 상에서 시작점으로 부터

 

1. 현재위치/2

2. 현재위치/3

3. 현재위치-1

4. 현재위치+1

 

으로 이동하는 BFS 문제라 볼 수 있다.

그럼 이제 A, B 사이의 소수를 도착점으로 하는 방법만 찾으면 된다.

 

B의 최대값은 100000이므로, 100000까지의 모든 소수만 찾으면 된다. 이 때, 당연하게도 매번 소수판정을 하면 시간초과가 날 것이다. 그러니 TC들 진행하기 이전에, 100000까지의 모든 소수를 찾아두면 된다. 이 경우 에라토스테네스의 체 방식으로 구해두면 편하게 소수를 구할 수 있다.

이 때 100000의 square root 까지만 확인해보면 되는데, 이에 대한 증명은 아래와 같다.

 

 

전체 로직을 정리하면 다음과 같다.

 

1. 프로그램 시작 시 우선 10만 이하의 모든 소수를 구해둔다.

 

2. 각 테스트 케이스에 대해 'N'에서 시작해서 BFS를 진행하며, A와 B 사이의 소수에 도달 시 거리를 출력한다.

 

 

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/17300/BOJ_17394.java

import java.io.DataInputStream;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;

public class Main {
    HashSet<Integer> pn;

    private void initPn() {
        pn = new HashSet<>();
        boolean[] arr = new boolean[100001];
        for (int i = 2; i <= Math.sqrt(100000); i++) {
            if (arr[i]) continue;
            int base = i+i;
            while (base <= 100000) {
                arr[base] = true;
                base += i;
            }
        }
        for (int i = 2; i <= 100000; i++) {
            if (!arr[i]) pn.add(i);
        }
    }

    private int bfs(int n, int a, int b) {
        int limit = Math.max(n, b);
        boolean[] v = new boolean[limit+1];
        int[] dist = new int[limit+1];
        Queue<Integer> q = new ArrayDeque<>();
        q.add(n);
        v[n] = true;
        while (!q.isEmpty()) {
            int cur = q.poll();
            if (a<=cur && cur<=b && pn.contains(cur)) {
                return dist[cur];
            }
            for (int i = 0; i < 4; i++) {
                int next = cur;
                switch (i) {
                    case 0 : next/=2; break;
                    case 1 : next/=3; break;
                    case 2 : next+=1; break;
                    case 3 : next-=1; break;
                }

                if (next<0 || next>limit || v[next]) continue;
                v[next] = true;
                dist[next] = dist[cur] + 1;
                q.add(next);
            }
        }
        return -1;
    }

    private void solution() throws Exception {
        initPn();
        int tc = nextInt();
        StringBuilder sb = new StringBuilder();
        while (tc-->0) {
            int n = nextInt();
            int a = nextInt();
            int b = nextInt();
            sb.append(bfs(n, a, b)).append('\n');
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }

    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    private static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    private static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        boolean neg = (c == '-');
        if (neg) c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        if (neg) return -ret;
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}