백준 1644번 - 소수의 연속합(C++)

문제

• 백준, 골드 3, 문제 링크
• 풀이 날짜: 2025.05.18
• 풀이 시간: 23:05~00:11
• 사용 언어: C++

문제 해설

연속된 소수의 합은 2D 테이블로 표현할 수 있다.

$table[i][j]$ = {i번째 소수부터 j번째 소수까지 연속된 소수의 합}
(단, 0 ≤ i ≤ j인 정수 i, j)

일반적으로 N 이하의 모든 소수에 대해서는 해당 테이블은 평균적으로 sqrt(N) * sqrt(N)의 셀이 존재한다고 알려져 있다.

i > 0일 때, $table[i][j] = table[0][j] - table[0][i-1]$로 나타낼 수 있다. 왜냐하면, 3~5번째의 연속된 소수의 합은 1~5번째 소수 합에서 1~2번째 연속된 소수의 합을 빼면 되기 때문이다. 이런 식으로 계산하면, table의 첫 번째 행만 계산해도 전체 테이블을 계산할 수 있다.

또한 i = 0인 첫 번째 행에 대해서는 p[k]가 k번째 소수라고 하면 table[0][k] = table[0][k-1] + p[k]로 간단히 DP를 통해 구할 수 있다.

이 점을 고려하면, 하나의 셀을 구하는 데에는 상수 시간(O(1))이 걸리므로, 모든 셀을 돌아가면서 합이 N이 되는 값을 구하는 데에는

셀의 개수 * 처리 시간 = ~N * O(1) = ~O(N)의 시간이 소요된다.

이때, N 이하의 모든 소수를 구할 때 에라토스테네스의 체를 이용하면 $O(nloglogn)$의 시간 복잡도를 갖게 될 것이다.

그런데 모든 셀을 계산하는 건 사실 지나치게 비효율적이므로 좀 더 최적의 방법을 찾아보자.

예시 입력 테스트하기

예시 입력 20에 대해, table은 아래와 같다.

tab 02 03 05 07 11 13 17 19

02   2  5 10 17 28 31 48 67

03      3  8 15 26

05         5 12 23

07            7 18 21

11              11 14 31

13                 13 30

17                    17 38

19                       19

이때, 편의상 i행 j열의 요소를 table[i][j]라 칭하겠다.

여기서 목표는 20과 같은 값을 찾는 것이므로, 첫 번째 줄 이외에서는 n=20을 초과하는 값이 나오면 그 이후는 기록하지 않았다.

규칙을 살펴보자면, 각 행마다 왼쪽에서 살펴보면서 20보다 크거나 같은 수가 나오면 다음 행으로 넘어 가도록 했다. 이후에 나오는 숫자는 20보다 계속 커질 것이기 때문이다.

이때 한 가지 특이한 점이 있다면, i번째 행에서 table[i][j]까지 검사했다면, i+1번째 행에서는 제일 먼저 검사해야 할 요소는 맨 첫 번째 요소인 table[i+1][i+1]이 아니다. 검사해야 할 곳은 table[i+1][j]일 것이다.

그 이유는, 위 테이블을 보면 알겠지만 윗쪽 행에서 아래 행로 내려올수록 같은 열에서 값이 점점 낮아지기 때문이다.

왼쪽에서 오른쪽으로 검사하면 table[i][j]에서는 n보다 크거나 같은  table[i][j-1] < n보다 작을 것이다. 모든 행에 대해서 i번째 행보다는 i+1번째 행의 요소가 더 작다. 즉, table[i+1][j-1] < table[i][j-1]이다. 즉, j번째 이전의 항에서는 무조건 n보다 작은 값만 나타나게 될 것이다.

그래서 i번째 행에서 0번째 열부터 j번째 열까지 조사했을 때 N보다 큰 값이 나왔다면, 다음 i+1행에서는 j번째 열부터 조사하면 되는 것이다. 

이렇게 하면 조사할 곳은 각 행마다 몇 개의 요소를 조사하지 않아도 된다. 즉, 조사할 셀의 개수를 '소수의 개수'에 비례한 수준으로 최적화할 수 있다.

다만 처음에 합이 N이 되는 소수를 구할 때 시간이 많이 걸리는데, 아무리 많이 해도 (N 이하의 소수의 개수)만큼만 검사하면 되므로 최초 조사 인덱스도 구하기 쉽다.

정리하면 이렇다.

시간 복잡도: NloglogN

공간 복잡도: sqrt(N)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool isPrime[4000001];
void primeSieve(int maxN, vector<int>& outPrimes)
{
    fill_n(isPrime, maxN + 1, true);

    outPrimes.reserve(maxN + 1);

    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= maxN; i++)
    {
        if (isPrime[i])
        {
            for (int j = i * i; j <= maxN; j += i)
                isPrime[j] = false;
        }
    }

    for (int i = 2; i <= maxN; i++)
    {
        if (isPrime[i])
            outPrimes.push_back(i);
    }
}

int dp[4000001];

inline int getConsecutivePrimeSum(int i, int j)
{
    if (i == 0)
        return dp[j];
    else
        return dp[j] - dp[i - 1];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;

    cin >> n;

    // 1. 체 방식으로 소수 구하기
    vector<int> primes;
    primeSieve(n, primes);

    // 2. table 구하기
    dp[0] = primes[0];
    for (int i = 1; i < primes.size(); i++)
    {
        dp[i] = dp[i - 1] + primes[i];
    }

    // 3. 최초 인덱스 찾기
    int result = 0;
    int idx = 0;

    for (int i = 0; i < primes.size(); i++)
    {
        while (idx < primes.size() && getConsecutivePrimeSum(i, idx) < n)
            idx++;

        if (idx >= primes.size())
            break;
        if (getConsecutivePrimeSum(i, idx) == n)
        {
            result++;
        }
    }
    cout << result;

    return 0;
}

문제를 풀 때 생긴 문제점

이때 문제를 푸는데 첫 줄의 idx를 처음부터 구하려고 하면 너무 비효율적일 것 같았다. 그 때문에 dp를 이분 탐색하여 n인 값을 구하려고 했는데, 그런데 시작 인덱스를 다음과 같이 구하니 문제가 생겼다.

// 3. 최초 인덱스 찾기
int* pi = lower_bound(dp, dp + primes.size(), n);

int idx = (int)(pi - &dp[0]);

이론적으로는 문제가 없을 줄 알았는데, 왜 문제가 생겼을까?

분석해보니, 원인은 ‘소수의 합의 범위가 int의 범위를 초과했기 때문’이다.

n=4,000,000일 때 dp를 조사해 보았다.

딱 57134번째 소수까지의 합이 2147129760인데 그다음이 -2147129705로 int를 초과했다.

한 인덱스씩 넘기면서 선형적으로 조사한다면 n, 즉 400만을 넘는 순간 다음 줄로 넘어가기 때문에 그리 큰 문제가 안된다.

그러나 2부터 400만 이하의 가장 큰 소수의 합을 모두 더하면 그것은 int의 범위를 훌쩍 넘기 때문에, 이 dp 전체를 이분탐색하게 되면 이상한 결과가 나온다. 값의 범위로 인해 dp는 정렬되지 않게 되었고, 그로 인해 이분 탐색이라는 방법은 사용할 수 없게 된 것이다.