[BOJ] 2960번: RESETO

문제

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

이 알고리즘은 다음과 같다.

1. 2부터 N까지 모든 정수를 적는다.
2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

 

입출력 예시

 

풀이

에라토스테네스의 체는 굉장히 유명한 유형임에도 불구하고 볼 때마다 새로운 느낌이다. 풀이를 완전히 외워두던가 해야겠다.

 

아래는 문제를 보고 내 머릿속에 떠올랐던 생각들이다.

 

◾ 지워진 숫자가 몇 번째인지 세기 위한 변수가 필요함 → cnt 변수 정의

◾ cnt를 정의했다면, 변수를 갱신하는 시점을 설정해야 함

 

변수 갱신 시점은 6, 12처럼 여러 수의 공배수를 처리하기 위해 필요하다. N=7이라면 [2, 3, 4, 5, 6, 7]과 같은 정수 리스트가 만들어질 것이고, 지워지는 숫자의 순서는 2 → 4 → 6 → 3 →  5 →  7이 된다. 이 때 특정 조건 없이 cnt에 계속 +1을 하다 보면 6은 이미 지워졌는데도 3의 배수에서 걸리기 때문에 cnt 값이 이상하게 저장되어 버린다.

 

이런 경우를 방지하기 위해 remove_check라는 리스트를 사용했다.

 

remove_check 리스트의 역할은 이미 지워진 숫자라면 해당 인덱스 값을 1로 바꾸는 것으로, remove_check 값이 1이 아닐 때만(=아직 안 지워졌다는 뜻) cnt 값을 1씩 증가시킨다.

 

 cnt 값이 K랑 같아지는 시점이 오면 해당 값을 바로 출력한 후 모든 for문을 탈출하면 해결!

 

..이긴 한데 뭔가 내용이 깔끔하게 정리되지 않은 듯한 이 느낌 😶

 

# Silver 4

import sys

N, K = map(int, sys.stdin.readline().split())

integer_list = [num for num in range(2, N+1)]

remove_check = [0]*(N+1)

remove_check[0] = remove_check[1] = 1

cnt = 0

for i in range(2, N+1):
    for j in range(i, N+1, i):
        if remove_check[j] != 1:
            remove_check[j] = 1
            cnt += 1

        if cnt == K and remove_check[j] == 1:
            print(j)
            exit()

 

 

값을 출력하기 전에 remove_check[j] 값이 1인지 확인하는 조건문을 지우니까 시간이 좀 더 걸렸는데 아직 이유는 파악하지 못했음