[백준알고리즘] 1644번: 소수의 연속합 -Python

[백준알고리즘] 1644번: 소수의 연속합 -Python

https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

연속합 형태의 문제와 똑같이 풀어주나 소수를 구하는 과정이 추가된다.

다른 부분들을 똑같이 하더라도 소수를 구하는 과정에 쓸데없는 과정이 더 생길 경우 시간 초과가 발생할 수도 있는 것 같다.

 

소수를 구하는 과정은 에라토스테네스의 체를 그대로 사용했다.

 

 

연속합을 구해주는 과정은 더블 포인터를 사용하지 않아도 해결할 수 있는 문제다.

그래서 처음에는 더블 포인터를 사용하지 않고 통과를 했었다.

 

소수들을 뒤에서부터 역순으로 검색한 이유는 소수간의 간격이 수가 커질수록 점점 커진다는 것을 이용해서 조금이나마 시간을 줄이기 위해서였다.

n = int(input())
 
num = [1] * (n+1)
for i in range(2, n+1):
    if num[i]:
        t = 2
        while i * t <= n:
            num[i * t] = 0
            t += 1
 
ans = 0
for i in range(n, 1, -1):
    if num[i]:
        tmp = 0
 
        for j in range(i, 1, -1):
            if num[j]:
                tmp += j
 
                if tmp == n:
                    ans += 1
                    break
                elif tmp > n:
                    break
 
print(ans)

 

더블 포인터를 이용한 코드는 아래와 같다.

2에 대한 예외처리가 안됐어서 한 번 틀렸었다...ㅎㅎ..

n = int(input())
 
num = [True] * (n+1)
num[0] = num[1] = False
for i in range(2, n + 1):
    if num[i]:
        t = 2
        while i * t <= n:
            num[i * t] = 0
            t += 1
 
prime = sorted([i for i in range(2, n+1) if num[i]], reverse=True)
len_prime = len(prime)
ans = 0
 
if len_prime >= 1:
    lo, hi, tmp = 0, 1, prime[0]
    while lo < len_prime:
        if tmp >= n:
            if tmp == n:
                ans += 1
            tmp -= prime[lo]
            lo += 1
        # tmp < n
        elif hi == len_prime:
            break
        else:
            tmp += prime[hi]
            hi += 1
 
print(ans)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다