[백준1644/골드3] 소수의 연속합 - Python

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

 

소수를 빠르게 구할 때 에라토스테네스의 체로 구한다는거 알고만 있고, 그게 어떤 방식인지 몰라서 먼저 백준 2960 - 에라토스테네스의 체 문제 먼저 풀어봤다.

그리고 이 문제는 N까지의 수 중, 소수만 따로 리스트를 만들고 시작했다.

 

# 2부터 N까지의 수 중, 소수만 담긴 리스트 반환하기

N = int(input())

def prime(n):

    numbers = [True] * (n+1)
    numbers[0] = numbers[1] = False

    for i in range(2, n+1):

        if numbers[i]:
            for j in range(2 * i, n+1, i):
                numbers[j] = False

    return [k for k in range(n+1) if numbers[k]]

prime_lst = prime(N)

 

 

그리고 그 배열에서 연속된 수의 합이 N이 되는 수를 찾으려고 했다.

처음엔

1. 누적합을 구한 후, 누적합이 N인 인덱스부터 순회

2. 누적합이 N보다 크면 그보다 작은 누적합들을 이중for문으로 순회하면서 누적합의 차가 N이 되면 cnt += 1

이런 식으로 구하려고 했는데 너무 복잡해져서 투포인터로 전환했다.

 

투포인터 계산 방식

1. left, right 0부터 시작

2. right += 1 하면서 현재 합에 소수 더하기

3. 현재 합이 N이 되면 cnt += 1

4. 현재 합이 N 이하라면 지금 포인터 내의 수 중 제일 오른쪽 수 (prime_list[right]) 더해주고 다른 경우의 수 탐색

5. 현재 합이 N 초과라면 지금 포인터 내의 수 중 제일 왼쪽 수 (prime_list[left]) 빼주고 left += 1 다른 경우의 수 탐색

6. 범위 벗어나면 while 문 종료

 

# 성공 코드

N = int(input())

def prime(n):

    numbers = [True] * (n+1)
    numbers[0] = numbers[1] = False

    for i in range(2, n+1):

        if numbers[i]:
            for j in range(2 * i, n+1, i):
                numbers[j] = False

    return [k for k in range(n+1) if numbers[k]]

prime_lst = prime(N)
left = 0
right = 0
cur = 0
cnt = 0

while left <= right <= len(prime_lst):
    if cur == N:
        cnt += 1

    if cur <= N:
        if right == len(prime_lst):
            break
        cur += prime_lst[right]
        right += 1

    elif cur > N:
        cur -= prime_lst[left]
        left += 1

print(cnt)