[백준 - 17394] 핑거 스냅 - Python

분류: 소수, bfs /

문제

문제 링크

문제 설명

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

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

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

 

풀이

- 내 풀이

from collections import deque
import math
import sys
read = sys.stdin.readline

# 소수 미리 계산
primes = [2]
for i in range(3, 100000, 2):
    r = math.sqrt(i)
    for p in primes:
        if p > r:
            primes.append(i)
            break
        if i % p == 0:
            break
    else:
        primes.append(i)

T = int(read())
for _ in range(T):
    N, A, B = map(int, read().split())
    
    # A와 B 사이 소수 추출
    primesBetweenAB = set()
    for p in primes:
        if p < A:
            continue
        if p > B:
            break
        primesBetweenAB.add(p)
        
    # A와 B 사이에 소수가 없으면 -1
    if len(primesBetweenAB) == 0:
        print(-1)
        continue
    
    # 중복 계산을 막기위해 dp에 계산한 값 저장 {k: N부터 k까지 가는 최소 연산횟수}
    dp = {N: 0}
    
    # BFS
    q = deque([N])
    ans = -1
    while q:
        n = q.popleft()
        # n이 A와 B사이에 소수이면 N에서 n까지 가는 최소 연산횟수를 출력하고 종료
        if n in primesBetweenAB:
            ans = dp[n]
            break
        
        # 4가지 연산중 아직 방문하지 않은 수에 대해 다음 수를 큐에 넣고 BFS
        for next in filter(lambda x: not (x in dp or x<0), [n//2, n//3, n+1, n-1]):
            dp[next] = dp[n] + 1
            q.append(next)
    print(ans)

- 다른 사람 풀이

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

# 에라스토테네스의 체
check = [False, False] + [True] * 99999

for i in range(2, 100001):
    if check[i]:
        for j in range(2 * i, 100001, i):
            check[j] = False

t = int(input())
for _ in range(t):
    n, a, b = map(int, input().split())
    
    # 소수가 있는지 체크
    flag = True
    for i in range(a, b + 1):
        if check[i]:
            flag = False
            break
    
    if flag:
        print(-1)
        continue
    
    # 현재 수가 목표치보다 적어 늘리기만 해야할 경우
    if n < a:
        for i in range(a, b + 1):
            if check[i]:
                print(i - n)
                break
    
    else:
        # bfs
        visited = set([n])
        queue = deque([(n, 0)])
        
        while queue:
            now, count = queue.popleft()
            
            # 탈출 조건
            if now <= 100000 and check[now] and a <= now <= b:
                print(count)
                break
            
            # 3으로 나누기
            if (now // 3) not in visited:
                visited.add(now // 3)
                queue.append((now // 3, count + 1))
            # 2로 나누기
            if (now // 2) not in visited:
                visited.add(now // 2)
                queue.append((now // 2, count + 1))
            # 하나 늘리기
            if now < 100000 and (now + 1) not in visited:
                visited.add(now + 1)
                queue.append((now + 1, count + 1))
            # 하나 줄이기
            if now > 0 and (now - 1) not in visited:
                visited.add(now - 1)
                queue.append((now - 1, count + 1))

• N이 A보다 작은 경우 (A와 B사이 가장 작은 소수) - N으로 계산하는 것
• 전체 수를 리스트로 만들어 소수를 T/F로 저장하는 것
• 반복되는 코드가 싫어 `filter`와 `lambda`를 이용했지만 이분 처럼 반복해서 적는 것이 더 가독성이 좋을 때가 있고, +1과 -1처럼 개별 조건을 추가할 수 있다.
• 위 문제의 bfs에서 저장할 것은 3개이다. 나는 1은 `큐` 2, 3을 `해쉬 테이블로`에 저장했지만 이분은 1, 2를 `큐`, 3을 `셋`에 저장했다.
  1. bfs를 돌며 `현재 위치`를 나타내는 값(나는 n, next 이분은 now)
  2. 초기값 N에서 현재 위치까지의 `거리` (나는 dp 딕셔너리의 값, 이분은 count)
  3. 중복 계산을 막기위해 `memoization` (나는 dp 딕셔너리의 키, 이분은 visited 셋)