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

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

 

 

📋 문제

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다.

몇 가지 자연수의 예를 들어 보면 다음과 같다.

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

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다.

7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다.

또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

 

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

 

 

👉 입력

첫째 줄에 자연수 N이 주어진다.

(1 ≤ N ≤ 4,000,000)

 

 

👈출력

첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

 

 

💡 사용된 개념

✔️ 투 포인터 알고리즘(Two Pointers)

리스트에 순차적으로 접근해야 할 때 2개의 pointer의 위치를 기록하면서 처리하는 알고리즘을 의미한다.

투 포인터 알고리즘의 예시로 특정한 합을 가지는 부분 연속 수열 찾기 문제가 있다.

 

특정한 합을 가지는 부분 연속 수열 찾기는 자연수로 구성된 리스트가 주어질 때, 부분 연속 수열의 합이 특정값을 가지는 횟수를 카운트하는 문제이다.

 

 

이 문제에서 부분 연속 수열의 시작점을 start, 끝점을 end, 특정 부분합을 M이라고 할 때 구체적인 알고리즘은 다음과 같다.

 

1. start와 end가 주어진 리스트의 첫 번째 원소(인덱스 0)를 가리킨다.
2. 현재 부분합이 M과 같다면 카운트한다.
3. 현재 부분합이 M보다 작으면 end를 1 증가시킨다.
4. 현재 부분합이 M보다 크거나 같으면 start를 증가시킨다.
5. 모든 경우를 확인할 때까지 2 ~ 4의 과정을 반복한다.

 

이 문제에서는 start와 end의 위치를 기록해 부분합을 M과 비교하고 있다.

이러한 방식의 알고리즘이 투 포인터 알고리즘이다.

 

 

📝 풀이

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(input())
arr = prime_list(n+1)
start, end = 0, 0
total = 0
answer = 0

for end in range(len(arr)):
  total += arr[end]
  
  while total >= n:
    if total == n:
      answer += 1
    total -= arr[start]
    start += 1
print(answer)

 

2부터 입력받은 수까지의 범위 중 소수를 찾고 이들의 부분합이 입력받은 수가 되는 경우의 수를 찾는 문제였다.

 

먼저 소수를 찾아야 한다.

소수를 찾는 방법은 에라토스테네스의 체를 이용했다.

이때 n이 소수이면 n도 포함해야 하므로 소수를 구하는 범위는 n+1까지로 설정했다.

 

이후 움직일 포인터인 start와 end를 모두 0으로 초기화했고 부분합을 저장할 변수 total을 선언했다.

end가 arr의 범위를 순회하며 total에 arr의 요소들을 더해나간다.

 

total이 n과 같거나 커지는 순간이 오면 두 번째 while문에 진입한다.

여기서 total이 n과 같다면 부분합이 n과 같은 경우를 찾은 것이므로 answer에 1을 더한다.

 

total이 n과 같지 않고 n보다 크다면 start를 움직여 start에 해당하는 요소를 뺀다.

그리고 다시 n보다 작아지면 end를 움직여 합을 더해가는 식이다.

 

 

 

 

🔍 참조

이것이 취업을 위한 코딩 테스트다 with 파이썬 (한빛미디어, 나동빈)