백준 17394 (핑거 스냅) - java

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

 

문제

[어벤져스] 시리즈를 보지 않은 사람이라도 ‘인피니티 건틀렛’이 무엇인지는 다들 알 것이다. 그래도 모르는 사람들을 위해 설명을 하자면, 인피니티 스톤이 모두 모인 인피니티 건틀렛을 끼고 손가락을 튕기면, 사용자가 원하는 것을 할 수 있다. 그러나 반동이 매우 심하기 때문에 그리 많이는 사용할 수 없다.

정신 나간 수학자 Sonaht는 우연히 이 인피니티 건틀렛을 손에 넣게 된다. 그러나 이 인피니티 건틀렛에는 약간의 하자가 있어서, 핑거 스냅으로 할 수 있는 일이 몇가지 없다. 다음은, 핑거 스냅으로 할 수 있는 일을 나열한 것이다.

1. 전 우주의 생명체 수를 현재의 절반으로 한다.
2. 전 우주의 생명체 수를 현재의 1/3로 한다.
   (위의 두 경우에서, 나누어 떨어지지 않으면 몫만 남기고, 나머지는 버린다.)
3. 전 우주의 생명체 수를 현재보다 하나 늘린다.
4. 전 우주의 생명체 수를 현재보다 하나 줄인다.
   (이미 전 우주의 생명체 수가 0이라면 할 수 없다.)

Sonaht는 전 우주의 생명체 수를 목표치 A 이상 B 이하로 줄이려 한다. 그러나 역시나 정신 나간 수학자답게, A 이상 B 이하인 수 중 소수로 만들려 한다. (어쩌면 A와 B 사이에 소수가 없을지도 모르지만 말이다.) 소수란, 서로 다른 약수가 1과 자기 자신밖에 없는 수를 의미한다. 그러나 인피니티 건틀렛은 반동이 심하기에, Sonaht는 최대한 적은 수의 핑거 스냅으로 이 목표를 달성하고자 한다. Sonaht가 최소 몇 번의 핑거 스냅을 해야 할지 구해보자.

 

유형 : BFS

 

접근 방식

• 3번 연산 즉 +1 연산의 조건은 1_000_000 이하이다.
• 에라토스테네스의 체로 미리 소수를 구해놓는다.

 

코드

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

public class BOJ_17394_핑거_스냅 {

    static int t,n,a,b;
    static boolean[] isPrime = new boolean[1_00_001];

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

        makePrime();

        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        t = Integer.parseInt(st.nextToken());


        StringBuilder sb = new StringBuilder();

        for(int tt = 1 ; tt <= t ; tt++) {
            st = new StringTokenizer(br.readLine()," ");
            n = Integer.parseInt(st.nextToken());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());

            int tmp = go();

            sb.append(tmp).append("\n");
        }

        System.out.print(sb);
        br.close();
    }

    static int go() {
        int result = -1;
        Queue<Integer> q = new ArrayDeque<>();
        int[] v = new int[1_000_001];
        q.add(n);
        v[n] = 1;

        while(!q.isEmpty()) {
            int cur = q.poll();

            if(cur >= a && cur <= b && !isPrime[cur]) {
                return v[cur] - 1;
            }

            int half = cur / 2;
            if(v[half] == 0) {
                v[half] = v[cur] + 1;
                q.add(half);
            }

            int talf = cur / 3;
            if(v[talf] == 0) {
                v[talf] = v[cur] + 1;
                q.add(talf);
            }

            if(cur + 1 <= 1_000_000) {
                if(v[cur + 1] == 0) {
                    v[cur + 1] = v[cur] + 1;
                    q.add(cur + 1);
                }
            }

            if(cur - 1 >= 0 && v[cur - 1] == 0) {
                v[cur - 1] = v[cur] + 1;
                q.add(cur - 1);
            }
        }

        return result;
    }


    static void makePrime() {
        for(int i = 2 ; i <= Math.sqrt(1000_00) + 1 ; i++) {
            if(!isPrime[i]) {
                int j = 2;

                while(i * j <= 1000_00) {
                    isPrime[i*j] = true;
                    j += 1;
                }
            }
        }
    }
}