[백준-파이썬] 17394: 핑거 스냅

문제 보러 가기!

접근 💚

처음에는 소수가 나와서 어떻게 접근할지 고민했다.
우주 생명체 수 N에서 핑거 스냅으로 할 수 있는 4가지 일을 하고, 그게 A와 B 사이의 소수인지 매번 확인하는 것은 힘들 것 같았다. (매번 소수인지 쭉 계산을 해야 하니까.)
그래서 좀 생각을 바꿔봤다! A, B는 100000 이하니까 10만 이하의 소수를 모~두 구하는 것이다. (에라토스테네스의 체로 구했다.)
그리고 A 이상 B 이하의 소수들을 리스트에 저장해두고, 핑거 스냅으로 4가지 일을 한 후에 그 우주 생명체 수가 그 리스트의 값들 중에 있는지 보는 것이다.

최소 몇 번의 핑거 스냅을 해야 할지 구하는 것! 즉 최단 거리를 구하는 것과 같으니까 BFS로 풀었다.

4가지 일을 한 후의 우주 생명체 수를 보고 범위 체크, 방문 체크를 해준 후에 만족하면 deque에 넣었다. 우주 생명체 수는 0 미만은 될 수 없고(이미 우주 생명체 수가 0이라면 현재보다 하나 줄일 수는 없고, 0//2나 0//3은 0이다.) 1,000,000 초과가 될 수는 없다고(N은 최대 1,000,000이고 우리의 타겟 범위는 최대 100,000이다. 인피니티 건틀렛으로 할 수 있는 일 중에서 생명체 수를 늘리는 것은 하나 늘리는 일밖에 없는데, 1,000,000보다 늘리는 것은 답과 멀어질 뿐이니까) 보았다.

처음에 틀린 코드 🤣

import collections
import sys

input = sys.stdin.readline

T = int(input())

# 십만 이하 소수 구하기
primes = [True] * 1000001
primes[0] = False
primes[1] = False

for i in range(2, 100000):
    if primes[i] == True:
        for j in range(i * 2, 100000, i):
            primes[j] = False


def sol():
    Q = collections.deque()
    visited[N] = True
    Q.append((N, 0))  # 현재 생명체의 수, 핑거 스냅 횟수

    while Q:
        life_cnt, finger_snap_cnt = Q.popleft()

        if life_cnt in target_primes:  # 목표 생명체 수이면
            return finger_snap_cnt

        finger_snap_results = [life_cnt // 2, life_cnt // 3, life_cnt + 1, life_cnt - 1]
        for finger_snap_result in finger_snap_results:
            if 0 <= finger_snap_result <= 1000000 and visited[finger_snap_result] == False:  # 범위 내, 방문 안 했으면
                visited[finger_snap_result] = True  # 방문 처리
                Q.append((finger_snap_result, finger_snap_cnt + 1))
    return -1


for tc in range(T):
    N, A, B = map(int, input().split())
    visited = [False] * 1000001

    target_primes = []
    for i in range(A, B + 1):
        if primes[i] == True:
            target_primes.append(i)

    # 범위 내에 소수가 없다면
    if len(target_primes) == 0:
        print(-1)
    else:  # 소수가 있다면
        ans = sol()
        print(ans)

print()

틀렸던 것..!! 😎

두구두구 왜 틀렸을까??
인덱스 때문이었다..!
위에서는 소수를 구할 때 범위를 for j in range(i * 2, 100000, i):로 했다. 그러면 j 는 99999까지만 돌게 된다. 그 결과, 100000은 소수가 아니지만 primes[100000] = True로 있어서 틀렸던 것이다.
아래처럼 고치니 맞았다!

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