백준 - [Gold 3] 1644번 소수의 연속합

문제링크:https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

에라토스테네의 체와 투 포인터를 활용해야 하는 문제입니다. 단순하게 소수를 구했다가 시간초과의 늪에서 헤어나오질 못하고 투포인터의 while문 통과 조건도 잘못 걸어 애를 먹었던 문제입니다.

---

문제 설명

- 하나의 수가 주어지고 소수의 연속합으로 하나의 수가 만들어 지는 경우의 수를 구하는 문제입니다.

- 예시

 

• 3 : 3 (한 가지)
• 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
• 53 : 5+7+11+13+17 = 53 (두 가지)

---

 

 

풀이

1. 에라토스테네스 체

일단 소수리스트를 먼저 구해야 합니다. 여기서 에라스토테네스의 체를 활용해야 합니다.

아래는 에라토스테네스 체의 설명입니다.

찾고자 하는 수(n) 까지 True로 채운 리스트를 생성 한 후
2를 제외한 2의 배수, 3을 제외한 3의 배수, 5를 제외한 5의 배수,
... sqrt(n)의 배수는 모두 False로 바꾼다.
결국, 2~n까지 숫자들 중 True인 숫자들이 소수가 된다.

출처: https://leedakyeong.tistory.com/entry/python-소수-찾기-에라토스테네스의-체

2. 투포인터

두 번째로는 투포인터를 사용하여 연속 부분 합을 구해줘야 합니다.

투 포인터는 왼쪽 오른쪽 포인터를 주어 조건에 따라 포인터를 조정해나가며 푸는 방식입니다.

이 문제 같은 경우는 아래의 기준으로 조정합니다.

• 현재까지의 부분 합 <= 입력받은 수  왼쪽 포인터를 증가
• 현재까지의 부분 합 > 입력받은 수  오른쪽 포인터를 증가
• 오른쪽 포인터가 끝까지 가면 종료

코드

from sys import stdin
stdin = open("input.txt", "r")
# 숫자 입력
N = int(stdin.readline())

# 에라토스테네스의 체 
# 출처: https://leedakyeong.tistory.com/entry/python-소수-찾기-에라토스테네스의-체
prime = [True] * (N+1)
for i in range(2, int(N ** 0.5) + 1):
    if prime[i]==True:
        for j in range(i+i, N+1, i):
            prime[j]=False

# N이하의 소수 구하기
prime_list = [i for i in range(2, N+1) if prime[i]==True]

# 투 포인터 변수(start, end) / 현재 합 변수 / 정답 카운트
start, end, cur_sum, answer = 0, 0, 0, 0

length = len(prime_list)

while True:
    
    # 현재합이 N보다 커지면 왼쪽 포인터만 이동
    if N <= cur_sum:
        cur_sum -= prime_list[start]
        start += 1
    
    # while문 종료조건: 오른쪽 포인터가 끝까지 갔을 경우
    elif end == len(prime_list):
        break
    
    # 현재합이 N보다 작아지면 오른쪽 포인터만 이동
    else:
        cur_sum += prime_list[end]
        end += 1
    
    # 숫자와 같을경우 정답 카운트
    if N == cur_sum:
        answer += 1

print(answer)

투 포인터가 어떻게 진행되는지 헷갈리는 분들은 아래 그림을 참조 하면 될 것 같습니다.

41 예제로 돌린건데 2+3+5+7+11+13 = 41 이다가 다음 숫자가 오면 41보다 커지므로 왼쪽 포인터를 증가시켜 3으로 시작하는 것을 확인할 수 있습니다.