https://www.acmicpc.net/problem/1644
이 문제는 다른 구간 합 문제와 동일하지만, 연속된 수가 아닌 연속된 소수의 구간 합을 구하는 문제이다.
때문에 연속된 소수를 구해야 했고, 이전에 풀었던 에라토스테네스의 체 개념을 적용해서 통과할 수 있었다.
에라토스테네스의 체란 무엇인가? 개념부터 잡고 가자.
<에라토스테네스의 체>
- 에라토스테네스가 만든 소수를 찾는 방법
- 마치 체로 치듯이 수를 걸러낸다고 하여 에라토스테네스의 체라고 부른다.
<찾는 과정>
ex) 100 이하의 자연수 중에서 소수를 찾아라.
1. 1부터 100까지 숫자를 쓴다.
2. 소수도 합성수도 아닌 1을 제거한다.
3. 2를 제외한 2의 배수를 제거한다.
4. 3을 제외한 3의 배수를 제거한다.
* 4는 제거할 필요 없다. (2의 배수에서 이미 지워진 상태)
5. 그 다음 소수인 5를 제외한 5의 배수를 제거한다.
6. 마지막으로 7을 제외한 7의 배수를 제거한다.
7. 그 다음 소수인 11부터는 배수를 지울 필요가 없다. (11 > $\sqrt{100}$이기 때문)
-> 소수를 찾는 방식 중 하나이다. 만약 1 ~ n 사이의 소수를 알고 싶다면, $\sqrt{n}$보다 작은 수의 배수만 체크해도 n 이하의 소수를 모두 찾는데 충분하다.
- 이렇게 해서 남은 수들이 100 이하의 소수가 되는 것이다.
- 따라서 만약 n 이하의 소수를 찾고 싶다면, 1부터 n까지 나열한 다음에 2의 배수, 3의 배수, 5의 배수, ..., $\sqrt{n}$의 배수까지 제거하면 된다.
<장점>
- 시간복잡도 : O(n log(log n)) -> 선형 시간에 동작할 정도로 빠르다.
- 때문에 다수의 소수를 찾아야 하는 문제에서 자주 사용
<단점>
- 알고리즘을 수행할 때, N의 크기만큼 리스트를 생성해야 하기 때문에 메모리가 많이 필요하다.
<code 구현>
- 인덱스 0 ~ n까지 중에 해당 인덱스 값이 True인 것만 소수로 판단하는 코드
def erato(N):
list = [False, False] + [True] * (N - 1) # 인덱스를 실제 수와 동일시 하여 리스트 초기화
for i in range(2, int(N**0.5) + 1): # 2부터 N의 제곱근까지 반복
if list[i]: # 2, 3, 5, 7 등 처음 나오는 숫들은 소수이기 때문에 해당 수들은 제외하고
for j in range(2 * i, N + 1, i): # 현재 소수의 배수들만 False로 변경
list[j] = False
return list- 위의 코드에서 만약 2의 배수를 지워서 4가 False가 됐다면, 나중에 list[4]의 값을 확인할 때 이미 False로 전환되었으므로 별다른 작업 없이 넘어가게 된다.
정답 코드이다.
Code #1
import sys
input = sys.stdin.readline
def erato(N): # 에라토스테네스의 체
final = [] # 소수만 저장될 리스트
list = [False, False] + [True] * (N - 1)
for i in range(2, int(N**0.5) + 1):
if list[i]:
for j in range(2 * i, N + 1, i):
list[j] = False
# 소수만 True로 유지된 상태에서 소수만으로 이루어진 리스트를 만들기 위한 코드
for i in range(N + 1):
if list[i]: # 현재 숫자가 소수라면,
final.append(i) # 리스트에 저장
return final # 소수만 저장된 리스트 반환
N = int(input())
sosu = erato(N) # 반환된 소수만 저장된 리스트로 초기화
tot = 0 # 구간 합 변수
left, right = 0, 0 # 투 포인터
result = 0 # 조건을 만족하는 구간 합 개수 (결과 변수)
while True:
if tot < N: # 구간합이 N보다 작을 때,
if right == len(sosu): # 현재 오른쪽 포인터가 리스트의 끝에 도달했다면,
break # 반복문 종료
# 아직 도달하지 않았다면,
tot += sosu[right] # 구간 합에 현재 오른쪽 포인터의 숫자 더하기
right += 1 # 오른쪽 포인터 한 칸 이동
elif tot == N: # 구간 합이 N과 같으면, 조건을 만족했으므로
result += 1 # 결과 변수 + 1
tot -= sosu[left] # 현재 구간 합에서 왼쪽 포인터가 가리키는 값 빼기
left += 1 # 왼쪽 포인터 한 칸 이동
else: # 현재 구간 합이 N보다 클 때,
tot -= sosu[left] # 현재 구간 합에서 왼쪽 포인터가 가리키는 값 빼기
left += 1 # 왼쪽 포인터 한 칸 이동
print(result)
위의 에라토스테네스의 체를 구현한 코드에서는 단순히 boolean 타입의 리스트를 반환했지만,
이 문제에서는 boolean 타입의 리스트를 반환해버리면 포인터가 하나의 인덱스씩 이동할 때마다 소수 여부를 검사해야 하기 때문에 아예 소수만으로 이루어진 리스트를 다시 생성해서 반환했다.
그냥 boolean 타입의 리스트를 반환해도 시간 초과가 나지는 않는다.
Code #2
import sys
input = sys.stdin.readline
def erato(N):
list = [False, False] + [True] * (N - 1)
for i in range(2, int(N**0.5) + 1):
if list[i]:
for j in range(2 * i, N + 1, i):
list[j] = False
return list
N = int(input())
sosu = erato(N)
tot = 0
left, right = 0, 0
result = 0
while True:
if tot < N:
if right == N + 1:
break
else:
if sosu[right]: # 현재 인덱스의 값이 True이면,
sosu[right] = right # 소수라는 뜻이므로, 해당 값을 인덱스 값으로 변경
else: # 현재 인덱스이 값이 False라면,
sosu[right] = 0 # 소수가 아니라는 뜻이므로, 0으로 변경
right += 1 # 다음 인덱스로 넘어가고,
continue # 아무런 추가 동작도 수행하지 않고 넘어간다.
tot += sosu[right]
right += 1
elif tot == N:
if sosu[left] == 0:
left += 1
continue
result += 1
tot -= sosu[left]
left += 1
else:
if sosu[left] == 0:
left += 1
continue
tot -= sosu[left]
left += 1
print(result)
위 코드는 에라토스테네스의 체 함수에서 boolean 타입의 리스트를 그대로 넘긴 경우인데, 위에서 말한 것처럼 모든 경우의 수에 조건식이 들어가 있어 코드가 훨씬 복잡하다.
사실 소수만으로 이루어진 리스트를 다시 생성할 때, for문을 한 번 더 돌기 때문에 시간이 더 오래걸리지 않을까라는 생각을 했지만, 오히려 모든 경우에 조건식이 달려있는 코드가 더 오래 걸렸다.
복잡하기도 하고, 오래 걸리기도 하니 1번 코드를 참고하자.