[Python/BOJ] 17394. 핑거 스냅

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을 출력한다.

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

풀이

Code

import sys
from collections import deque
input = sys.stdin.readline

# 1. 소수 판별 함수 정의
def check() :
    global number

    number[0], number[1] = False, False
    # 1-1.
    for i in range(2, 1_000_001) :
        # 해당 수가 소수일 경우
        if number[i] :
            for k in range(i*2, 1_000_001, i) :
                # 소수 여부 처리
                number[k] = False
# 2. bfs 함수 정의
def bfs(now) :
    # 2-1. 큐에 (현재 위치, 0) 삽입
    queue = deque()
    queue.append((now, 0))
    # 2-2. 방문 여부 리스트 생성 후 현재 위치 방문 처리
    visited = [False] * 1_000_001
    visited[n] = True
    # 2-3.
    while queue :
        # (위치, 핑거 스냅 횟수) 반환
        now, count = queue.popleft()
        #
        for next in [now // 2, now // 3, now + 1, now - 1] :
            # 예외 처리
            if next <= 0 or next > 1_000_000 : continue
            # 종료 조건
            if next in array : return count + 1 # 핑거 스냅 횟수 + 1 반환
            # 해당 위치에 방문하지 않은 경우
            if not visited[next] :
                # 방문 처리
                visited[next] = True
                # 큐에 (다음 위치, 핑거 스냅 횟수 + 1) 삽입
                queue.append((next, count + 1))

number = [True] * 1_000_001
# 3. 소수 판별 함수 실행
check()
t = int(input())
for _ in range(t) :
    n, a, b = map(int, input().split())
    # 4. 목표 범위 안의 소수 리스트 생성
    array = [i for i in range(a, b+1) if number[i]]
    # 5. 목표 범위 안에 소수가 없는 경우
    if not array : ans = -1
    # 6. 현재 생명체 수가 목표 범위 안에 들고 소수인 경우
    elif a <= n <= b and n in array : ans = 0
    # 7. 이외의 경우
    else :
        # bfs 실행
        ans = bfs(n)
    # 8. 결과 출력
    print(ans)