백준 알고리즘 1644번: 소수의 연속합

문제 정보

---

1644번: 소수의 연속합

 

 

핵심

---

일반 풀이와 투 포인터를 활용한 풀이가 두가지가 있다

무조건 에라토스테네스의 체 알고리즘을 활용하여 문제를 풀이하여야 하며 해당 개념은 이전에 올렸던 글에서 참고할 수 있다 (아래 참고 링크 확인)

위 두가지 풀이 모두 파이썬 기준 백준 제출시 통과되지만, 효율성은 투 포인터가 훨씬 좋다

 

 

풀이

---

일반 풀이

import sys
N = int(sys.stdin.readline())

prime = [True for _ in range(N+1)]
prime[0], prime[1] = False, False

for i in range(2, int(N**0.5) + 1):
    if prime[i]:
        j=2
        while i*j<=N:
            prime[i*j] = False
            j+=1

primes = [i for i in range(2, N+1) if prime[i]]
result = 0

for p in range(len(primes)):
    tmp = 0
    for a in range(p, len(primes)):
        tmp += primes[a]
        if tmp == N:
            result += 1
            break
        elif tmp > N:
            break

print(result)

 

1. 에라토스테네스의 체 알고리즘을 통하여 N까지의 소수 구하기

prime = [True for _ in range(N+1)]
prime[0], prime[1] = False, False

for i in range(2, int(N**0.5) + 1):
    if prime[i]:
        j=2
        while i*j<=N:
            prime[i*j] = False
            j+=1

primes = [i for i in range(2, N+1) if prime[i]]

해당 과정을 거침으로써 사용자가 입력한 N까지의 소수를 구할 수 있고,

해당 소수는 primes 배열에 넣어준다

 

2. 소수의 연속합 구하기

result = 0
for p in range(len(primes)):
    tmp = 0
    for a in range(p, len(primes)):
        tmp += primes[a]
        if tmp == N:
            result += 1
            break
        elif tmp > N:
            break

print(result)

0부터 N까지의 소수 개수(len(primes))를 반복하는 p에 대하여

p부터 len(primes) 까지의 숫자들을 차례로 더해가면서 수들의 합이 우리가 원하는 target인 N에 도달하면 result를 1 올려주고 반복을 마치며, 만일 합이 target을 초과한 경우에는 반복을 마친다

 

이러한 과정을 통해서 우리는 연속된 소수들의 합 중 target을 만족하는 개수를 구할 수 있다

 

 

투 포인터를 활용한 풀이

# 투 포인터를 활용한 풀이
import sys
N = int(sys.stdin.readline())

prime = [True for _ in range(N+1)]
prime[0], prime[1] = False, False

for i in range(2, int(N**0.5) + 1):
    if prime[i]:
        j=2
        while i*j<=N:
            prime[i*j] = False
            j+=1

primes = [i for i in range(2, N+1) if prime[i]]

start, end = 0, 0
total = 0
result = 0
# 범위 start <= total < end
while start <= end:
    if total >= N:
        total -= primes[start]
        start += 1
    elif total < N:
        if end == len(primes):
            break
        total += primes[end]
        end += 1
    if total == N:
        result += 1


print(result)

 

1. 에라토스테네스의 체 알고리즘을 활용한 소수 구하기

이는 위 풀이의 1번과 동일하다

 

2. 투 포인터를 활용하여 소수의 연속합 구하기

start, end = 0, 0
total = 0
result = 0
# 범위 start <= total < end
while start <= end:
    if total >= N:
        total -= primes[start]
        start += 1
    elif total < N:
        if end == len(primes):
            break
        total += primes[end]
        end += 1
    if total == N:
        result += 1


print(result)

start, end 그리고 start와 end 범위에 존재하는 소수들의 합을 의미하는 total을 선언하고

total이 우리가 원하는 target인 N보다 크거나 같으면 start 위치에 해당하는 소수를 total에서 빼고, start를 1씩 증가시킨다

만약 작으면 total에 end위치에 해당하는 소수를 total에 더해주고, end를 증가시킨다

다만, end가 len(primes) 이면, 반복을 중지시킨다

 

마지막으로 total이 target인 N과 같아지면 result를 하나씩 증가시켜 준다

해당 투 포인터 알고리즘에 대한 그림을 포함한 설명은 아래 참고링크의 다른 게시물을 통하여 정리해 두었으니, 보면 도움이 될 것이다!

 

 

참고

---

GitHub - dduneon/CodingTestPy

 

에라토스테네스의 체를 사용한 다른 문제

백준 알고리즘: 1978번 소수 찾기

 

투 포인터 알고리즘: 리스트에서 특정한 합이나 패턴 찾기

투 포인터 알고리즘: 리스트에서 특정한 합이나 패턴 찾기