[백준] 17394 핑거 스냅 (Python)

Algorithm (PS)

[백준] 17394 핑거 스냅 (Python)

minjiwoo 2023. 3. 22. 10:19

728x90

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

17394번: 핑거 스냅

[어벤져스] 시리즈를 보지 않은 사람이라도 ‘인피니티 건틀렛’이 무엇인지는 다들 알 것이다. 그래도 모르는 사람들을 위해 설명을 하자면, 인피니티 스톤이 모두 모인 인피니티 건틀렛을 끼

www.acmicpc.net

이문제는 BFS + 소수판별 알고리즘 이 핵심이었다.

오랜만에 에라토스테네스의 체를 정리해보았다.

https://sinclairstudio.tistory.com/492

에라토스테네스의 체 (소수판별 알고리즘) Python

에라토스테네스의 체 소수를 구하는 알고리즘 문제에서 주로 사용되는 풀이 방식이다. 1. 2 ~ N 까지의 자연수들 중에서, 아직 지워지지 않은 수들 중에서 가장 작은 수를 찾는다. 이를 p 라고 한

sinclairstudio.tistory.com

from collections import deque
import sys

input = sys.stdin.readline

INF = 1000000
primes = [True] * (INF+1) # 소수
primes[0] = False # 자연수 아님
primes[1] = False # 소수 될 수 없음
for i in range(2, int(INF**0.5)+1):
    if primes[i]:
        for j in range(i*i, INF, i): # i 의 배수들을 지우기
            primes[j] = False

def bfs(n, a, b):
    count = 0
    queue = deque([])
    queue.append((n, 0))
    visited = [False] * (INF+1)
    visited[n] = True
    while queue:
        now, count = queue.popleft()
        if a <= now <= b and primes[now]:
            return count
        snap1 = now // 2
        snap2 = now // 3
        snap3 = now + 1
        snap4 = now - 1

        if 0 <= snap1 <= INF and not visited[snap1]:
            visited[snap1] = True
            queue.append((snap1, count+1))
        if 0 <= snap2 <= INF and not visited[snap2]:
            visited[snap2] = True
            queue.append((snap2, count+1))
        if 0 <= snap3 <= INF and not visited[snap3]:
            visited[snap3] = True
            queue.append((snap3, count+1))
        if 0 <= snap4 <= INF and not visited[snap4]:
            visited[snap4] = True
            queue.append((snap4, count+1))

    return -1




T = int(input())

for i in range(T):
    N, A, B = map(int, input().split())
    print(bfs(N, A, B))

728x90