해결 과정
여러 개념들이 섞여 있는 문제다. 처음 풀이로는 시간 초과.
소수 찾기 - 에라토스테네스의 체
특히 이 문제는 투 포인터라는 개념을 알아야 했다.
즉, 연속적으로 이어진 배열의 합을 찾을 때, O(n*n)이 아니라, O(n) 선형 시간으로?
이 부분을 이해해보자.
나의 풀이
다음 두 글을 참고했다.
https://freedeveloper.tistory.com/393
def getNum(n, m, data):
count = 0
interval_sum = 0
end = 0
# start를 차례대로 증가시키며 반복
for start in range(n):
# end를 가능한 만큼 이동시키기
while interval_sum < m and end < n:
interval_sum += data[end]
end += 1
# 부분합이 m일 때 카운트 증가
if interval_sum == m:
count += 1
interval_sum -= data[start]
return count
def getPrimeByEratos(n):
a = [False,False] + [True]*(n-1)
primes=[]
for i in range(2,n+1):
if a[i]:
primes.append(i)
for j in range(2*i, n+1, i):
a[j] = False
return primes
def solution():
N = int(input())
answer = 0
arr = getPrimeByEratos(N)
# 투포인터 알고리즘으로 count 세기 -> O(n)???
return getNum(len(arr), N, arr)
print(solution())
'Coding Test > 문제 풀이' 카테고리의 다른 글
[문제 풀이] 무지의 먹방 라이브 (0) | 2022.03.24 |
---|---|
[문제 풀이] 백준 1439 (0) | 2022.03.24 |
[문제 풀이] 백준 5052 (0) | 2022.03.23 |
[문제 풀이] 백준 9935 (0) | 2022.03.23 |
[문제 풀이] 백준 1764 (0) | 2022.03.23 |