[BAEKJOON] 17394 핑거 스냅 (Java)

[ 문제 ]

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

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

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

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

입력

첫 번째 줄에 테스트 케이스의 개수 T가 주어진다. (1 ≤ T ≤ 10)

두 번째 줄부터 T개의 줄에 걸쳐, 현재 전 우주의 생명체 수인 자연수 N과, Sonaht의 목표 범위인 자연수 A, B가 공백으로 구분되어 주어진다. (2 ≤ N ≤ 1,000,000, 2 ≤ A ≤ B ≤ 100,000)

출력

매 줄마다, 각 테스트 케이스에서 Sonaht가 전 우주의 생명체 수를 목표범위 내의 소수로 만드는 데 필요한 최소한의 핑거 스냅의 횟수를 출력한다.

만약 목표범위 내의 소수로 만들 수 없다면, -1을 출력한다.

매 테스트 케이스는 독립적으로 고려되어야 한다.

[ 핵심풀이 ]

0) 4가지경우에 대해 bfs로 탐색하면 된다.

1) dp로 접근하는 방식도 있다고한다 <해보지 않아서 정확한 답안이 될 수 있는지 모름>

2) 탐색전 소수가 될 수 없다면 제외시킨다

3) 탐색전 이미 범위안에 있는 소수라면 0을 출력한다

4) 탐색중 범위안에있고 소수가되는 수가 될 시 출력한다

 

5) visit(방문)배열과 check(소수)배열의 인덱스 범위를 조정함에 있어 많이 틀렸다

방문배열은 2의 경우에 의해 최대범위*3까지 주어져야하는데,

이 최대범위는 문제에주어진 1백만이며, 입력으로 받은 값으로는 대체가 불가능했다.

소수배열은 10만까지 주어져 있기때문에 아래와같이 선언해주면 된다.

boolean visit[] = new boolean[3000001];
check = new boolean[100001];

[ 핵심소스 ]

result : 소수가 될 수 없는 경우 판별 (풀이 2번)

range : 소수안에 존재하는지 판별 (풀이 3번, 풀이 4번)

solve : (풀이 4번)

[ Java ]

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Pair {
    int value;
    int cnt;

    Pair(int value, int cnt) {
        this.value = value;
        this.cnt = cnt;
    }
    public int getValue() {
        return value;
    }
    public void setValue(int value) {
        this.value = value;
    }
    public int getCnt() {
        return cnt;
    }
    public void setCnt(int cnt) {
        this.cnt = cnt;
    }
}

public class _17394_핑거스냅 {
    static boolean check[];
    static void init() {
        Scanner sc = new Scanner(System.in);
        int TC = sc.nextInt();
        for (int t = 1; t <= TC; t++) {
            int index = sc.nextInt();
            int fs = sc.nextInt();
            int se = sc.nextInt();
			
            if (!result(fs, se))
                System.out.println(-1);
            else if (range(index, fs, se))
                System.out.println(0);
            else
                System.out.println(solve(index, fs, se));
        }
    }
    static boolean result(int fs, int se) {
        for (int i = fs; i <= se; i++) {
            if (!check[i])
                return true;
        }
        return false;
    }
	static int solve(int index, int fs, int se) {
        boolean visit[] = new boolean[3000001];
        Arrays.fill(visit, false);
		
        Queue<Pair>q=new LinkedList<Pair>();
        q.add(new Pair(index, 0));
        visit[index]=true;
        while(!q.isEmpty()) {
            Pair out = q.poll();
            if (range(out.getValue(), fs, se))	
                return out.getCnt();
			
            for(int i=0;i<4;i++) {
                int nv = out.getValue();
                int nc = out.getCnt()+1; 
                switch(i) {
                case 0:
                    nv/=2;
                    break;
                case 1:
                    nv/=3;
                    break;
                case 2:
                    nv+=1;
                    break;
                case 3:
                    nv-=1;
                    break;
                }
                if (nv <= 0 || visit[nv]) continue;
                visit[nv] = true;
                q.add(new Pair(nv, nc));
            }
        }
        return -1;
    }
    static boolean range(int value, int fs, int se) {
        return value >= fs && value <= se && !check[value];
    }
    static void eratostenes(int N) {
        check = new boolean[N];
        check[0] = true;
        check[1] = true;
        for (int i = 2; i < N; i++)
            for (int j = i + i; j < N; j += i)
                if (!check[j])
                    check[j] = true;
    }
    public static void main(String[] args) {
        eratostenes(100001);
        init();
	}
}