2960

날짜 : 2022. 09. 28

사용 언어 : python

 

문제

 

코드

# 에라토스테네스의 체
import sys
n, k = map(int, sys.stdin.readline().split())
nums = [] # 나열한 수
erase = [] # 지운 수
for i in range(2, n+1):
    nums.append(i)
while len(nums) > 0:
    p = nums[0] # 가장 작은 수 p
    temp = []
    for i in range(len(nums)):
        if nums[i] % p == 0: # p의 배수를 erase 리스트에 넣음
            erase.append(nums[i])
        else:
            temp.append(nums[i]) # 남아있는 숫자(p의 배수가 아닌 수)
    nums = temp
print(erase[k-1])

 

오답코드(이건 왜 오답인지 감이 안잡힌다..)

# 에라토스테네스의 체
import sys
n, k = map(int, sys.stdin.readline().split())
nums = [] # 나열한 수
erase = [] # 지운 수
for i in range(2, n+1):
    nums.append(i)
while len(erase) < k:
    p = nums[0] # 가장 작은 수 p
    temp = []
    for i in range(len(nums)):
        if nums[i] % p == 0: # p의 배수를 erase 리스트에 넣음
            erase.append(nums[i])
        else:
            temp.append(nums[i]) # 남아있는 숫자(p의 배수가 아닌 수)
    nums = temp
print(erase[-1])

 

 

알게된 점

- 문제에서 제시하는 에라토스테네스의 체를 구현하면서 2부터 n까지의 숫자를 넣은 리스트 nums

- 체를 쳐서 거른 수의 리스트 erase 작성

- nums에서 가장 작은 수 p를 통해 배수를 for문으로 거르는 방식으로 풀이

* 오답코드에서 볼 수 있듯 시간단축을 위해 지운 개수가 k개가 되면 while문을 탈출하는 방식으로 코딩했지만 오답이 나옴

왜일까...?

-> 반례 : 20 5 / print(erase[-1])을 사용한 경우 리스트의 가장 마지막 요소를 출력하지만 erase의 크기가 k보다 항상 같다는 보장이 없다.(오버된 상태로 while문을 탈출할 수 있기 때문)

=> 그래서 마지막 코드를 print(erase[k-1])로 수정했고 정답이 나왔다.

 

 

참고 사이트

-