[백준] 1644번 소수의 연속합 (파이썬, 두 포인터)

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

1644번: 소수의 연속합

 

오랜만에 아무것도 안찾아보고 푼 문제다.

하지만 풀고나서 사람들의 풀이를 보니 아직 나는 두 포인터를 활용하는 부분이 부족했던 것 같다.

 

코드를 보면서 더 설명하겠다.

 

import sys


def prime_list(n):
    sieve = [True] * n
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:
            for j in range(i+i, n, i):
                sieve[j] = False
    return [i for i in range(2, n) if sieve[i] == True]


n = int(sys.stdin.readline())
answer = 0
arr = prime_list(n+1)
l = len(arr)
for i in range(len(arr)):
    if i < l-1 and arr[i] + arr[i+1] > n:
        break
    p = i+2
    while(p <= l):
        if sum(arr[i:p]) == n:
            answer += 1
            break
        elif sum(arr[i:p]) < n:
            p += 1
        else:
            break

if l != 0 and arr[-1] == n:
    answer += 1

print(answer)

 

 

보면 알겠지만 for문을 돌려서 왼쪽 포인터의 값을 증가시키고 그 안에 while 문을 돌려서 오른쪽 포인터를 증가 시켰다.

내가 놓친 부분은 else 문이다.

else 후에 p는 초기화할 필요가 사실 없다.

예를 들어 i가 2이고 p가 6 일때 n보다 합계가 커진다면?

i =2, p=4에서 시작하는 것이 아니라 p=6에서 시작하는 것이 속도적으로 효율적일 것이다.

그리고 실제 사람들은 합계가 작으면 i를 올리고 크면 p를 줄이는 식으로 한 것 같다.

 

내 코드도 통과는 했지만 pypy로 돌려야만 풀렸으며 p를 i+2 가 아니라 len(arr) 부터 시작해서 줄여가는 형태로 만들었을 때는 시간 초과가 나왔다.

테스트 케이스 차이인것 같다.

 

다음에 두포인터 문제를 또 만나면 그때는 정석적인 방법으로 문제를 해결해봐야겠다.