[BOJ/Gold 5] 백준 17394 핑거 스냅(C++)

문제 링크

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

17394번: 핑거 스냅

 

 

문제

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

정신 나간 수학자 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을 출력한다.

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

예제 입력 1

5
9 2 4
100000 605 610
300 14 16
7 7 10
98765 500 550

예제 출력 1

1
15
-1
0
12

첫 번째 테스트 케이스에서는, 2번 동작 (전 우주의 생명체를 1/3로 줄임)을 하면 전 우주의 생명체의 수가 3이 되어, 2 이상 4 이하 소수가 된다. 그러므로 필요 횟수는 1이다.

세 번째 테스트 케이스에서는, 14 이상 16 이하 소수가 존재하지 않으므로, 아무리 핑거 스냅을 해도 목표를 달성할 수 없다. 따라서 -1을 출력한다.

네 번째 테스트 케이스에서는 핑거 스냅을 하지 않고도 목표가 달성되으므로 필요 횟수는 0이다.

알고리즘 분류

• 그래프 탐색
• 소수 판정

풀이

에라토스테네스의 체를 통해 소수를 판정한다.

이후 각 테스트케이스별로 BFS를 수행하여 4가지 동작들을 수행하면서 A와 B 사이에 존재하는 소수로 만들 수 있는 최소의 횟수를 구한다.

코드

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 1000001
#define INF 2e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int T, N, A, B;
int DP[MAX];
bool Visited[MAX];
int Answer;

void init() {
    for (int i = 2; i <= (MAX - 1); i++) {
        DP[i] = i;
    }
    for (int i = 2; i <= sqrt(MAX - 1); i++) {
        if (DP[i] == 0) {
            continue;
        }
        for (int j = (i * i); j <= (MAX - 1); j += i) {
            DP[j] = 0;
        }
    }
}

void init2() {
    Answer = INF;
    for (int i = 0; i < MAX; i++) {
        Visited[i] = false;
    }
}

bool checked(int Now) {
    if ((Now >= A) && (Now <= B)) {
        if (DP[Now] != 0) {
            return true;
        }
    }
    return false;
}

void BFS() {
    queue<pair<int, int> > Q;
    Visited[N] = true;
    Q.push(make_pair(N, 0));

    while (!Q.empty()) {
        int NowN = Q.front().first;
        int NowC = Q.front().second;
        Q.pop();

        if (checked(NowN)) {
            Answer = min(Answer, NowC);
            return;
        }

        int NextN = NowN / 2;
        if ((NextN >= 2) && (NextN < MAX) && !Visited[NextN]) {
            Visited[NextN] = true;
            Q.push(make_pair(NextN, NowC + 1));
        } 

        NextN = NowN / 3;
        if ((NextN >= 2) && (NextN < MAX) && !Visited[NextN]) {
            Visited[NextN] = true;
            Q.push(make_pair(NextN, NowC + 1));
        }

        NextN = NowN + 1;
        if ((NextN >= 2) && (NextN < MAX) && !Visited[NextN]) {
            Visited[NextN] = true;
            Q.push(make_pair(NextN, NowC + 1));
        }

        NextN = NowN - 1;
        if ((NextN >= 2) && (NextN < MAX) && !Visited[NextN]) {
            Visited[NextN] = true;
            Q.push(make_pair(NextN, NowC + 1));
        }
    };
}

void settings() {
    BFS();
}

void find_Answer() {
    if (Answer == INF) {
        cout << "-1\n";
    }
    else {
        cout << Answer << "\n";
    }
}

void input() {
    cin >> T;
    while (T--) {
        init2();
        cin >> N >> A >> B;
        settings();
        find_Answer();
    };
}

int main() {
    FASTIO
    init();
    input();

    return 0;
}