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

원본 링크

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

Intro

사실 이 문제는 아래의 두 가지 문제를 풀어봤다면 바로 짜깁기해서 풀 수 있는 문제이다. (우려먹기)

• 에라토스테네스의 체
  • 소수 구하기: https://www.acmicpc.net/problem/1929
• 두 포인터
  • 수들의 합 2: https://www.acmicpc.net/problem/2003

이 중 두 포인터문제는 예전에 한 번 다뤄 본 적이 있다.
혹시 풀이가 궁금하다면 하단의 링크를 참고하면 될 것 같다.

[백준 2003번] 수들의 합 2 풀이: https://rubpcase.tistory.com/32

문제

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

• 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을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

예제

예제 입력 1

20

예제 출력 1

0

예제 입력 2

3

예제 출력 2

1

예제 입력 3

41

예제 출력 3

3

예제 입력 4

53

예제 출력 4

2

주 알고리즘 분류

• 수학
• 정수론
• 두 포인터
• 소수 판정
• 에라토스테네스의 체

나만의 풀이

이 문제를 풀기 위해선 크게 2가지 챕터로 나눠서 구현을 해야 한다.
하나는 에라토스테네스의 체 알고리즘이며, 다른 하나는 두 포인터를 활용한 누적합 계산 과정이다.
여기서도 총 두 부분으로 나눠서 코드를 설명하려 한다.

에라토스테네스의 체는 소수 판정을 위한 방식 중 하나로, 체를 쳐서 크기가 상이한 입자들을 걸러내듯 소수를 솎아낸다고 보면 되겠다.
먼저 가장 작은 크기의 소수를 찾아낸다.
그 다음 이를 토대로 해당 소수의 배수들을 제거한다.
위 과정을 우리가 찾아내려는 범위에 관해서 전부 수행하면, 마지막에 남는 수들은 모두 소수가 된다.
이를 다음과 같이 코드로 구현할 수 있다.

import math

def erastothenes(n):  # 에라토스테네스의 체
    arr = [True] * (n+1)  # 0 ~ n

    for i in range(2, int(math.sqrt(n))+1):
        if arr[i]:
            j = 2
            while i*j <= n:
                arr[i*j] = False
                j += 1

    return [i for i in range(2, n+1) if arr[i]]

erastothenes()라는 함수로 정의를 했고, 해당 함수는 자연수를 입력 받아서 1 to n까지의 소수 배열을 return하게 된다.

먼저 arr라는 배열을 n+1개의 True값으로 선언했다.
그리고 첫 번째 소수인 2부터 앞서 말한 배수를 걸러내는 과정을 반복하게 된다.
이때, int(math.sqrt(n)), 즉 루트n보다 작거나 같은 정수를 기준까지만 탐색하게 된다.
자세히 증명하지는 않겠지만, 소수 판정을 위해서 해당 값까지만 탐색해도 됨은 자명하기 때문이다.
최종으로 True에 해당하는 인덱스만 리턴하면 소수 배열을 얻게 된다.

두 포인터를 활용한 탐색은 아까 인트로에서 말했듯, 다른 문제에서 다뤄본 적이 있다.
마치 퀵 정렬을 하는 것처럼 두 인덱스를 활용해서 값을 더해나가는 과정이라 보면 되겠다.
코드를 보면서 설명해보겠다.

i, j, s, c = 0, 0, lst[0], 0
l = len(lst)

while j < l:
    if s < n:
        j += 1
        if j < l: s += lst[j]
    elif s > n:
        s -= lst[i]
        i += 1
    else:
        c += 1
        s -= lst[i]
        i += 1
        j += 1
        if j < l: s += lst[j]

먼저 인덱스 용으로 i, j를 설정하고, i번째 원소부터 j번째 원소까지의 누적합 s와 일치 횟수 c를 초기화한다.
편의상 l이라고 lst 리스트의 길이를 설정했다.

이제, j가 배열 길이보다 작을 동안 while문을 돌면 된다.
이때, 현재까지의 누적합이 n보다 작으면, j를 증가하고 누적합을 더해주면 된다.
그 반대로 누적합이 큰 경우 누적합에서 값을 빼주고 i를 증가하면 된다.
정확하게 n인 경우에는 위 과정을 다 하고, 카운팅 값을 +1하면 된다.

최종적으로 전체 모듈과 출력까지 고려하면 다음과 같이 코드를 짤 수 있다.
참고로 중간에 if~else구문으로 감싼 이유는 n == 1인 경우를 처리하기 위해서이다.
에라토스테네스의 체 함수의 경우 n=1이면 빈 리스트를 전달하게 된다. (왜냐하면 1은 소수도 합성수도 아니니.)
따라서 1의 경우만 예외적으로 바로 print(0)구문으로 이어지도록 만들었다.

import math

def erastothenes(n):  # 에라토스테네스의 체
    arr = [True] * (n+1)  # 0 ~ n

    for i in range(2, int(math.sqrt(n))+1):
        if arr[i]:
            j = 2
            while i*j <= n:
                arr[i*j] = False
                j += 1

    return [i for i in range(2, n+1) if arr[i]]

n = int(input())

if n == 1:
    print(0)
else:
    lst = erastothenes(n)

    i, j, s, c = 0, 0, lst[0], 0
    l = len(lst)

    while j < l:
        if s < n:
            j += 1
            if j < l: s += lst[j]
        elif s > n:
            s -= lst[i]
            i += 1
        else:
            c += 1
            s -= lst[i]
            i += 1
            j += 1
            if j < l: s += lst[j]

    print(c)

마치면서

이 문제를 풀면서 사실 조마조마했던 게, 로컬에서 n = 4000000을 넣어서 돌리니까 2초를 넘겨서 결과가 출력되었다.
그래서 내가 잘못 코드를 짰는가 해서 일단 제출하니 통과가 되었다.
아마 내 로컬 인터프리터의 속도하고 백준 사이트의 코드 실행 속도하고 차이가 있어서 그런 것 같다.

아무튼 예전 문제들을 복기하는 느낌이라서 좋은 문제라고 생각했다.