[백준 / C++] 소수의 연속합 (골드 3, 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을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

예제 입력 1

20

예제 출력 1

0

예제 입력 2

3

예제 출력 2

1

예제 입력 3

41

예제 출력 3

3

예제 입력 4

53

예제 출력 4

2

---

문제 풀이

이번 문제는 특정한 수를 소수의 연속 합으로 나타낼 수 있는 경우의 수를 구하는 문제입니다.

 

문제를 풀기 위해 필요한 지식은 크게 2가지가 존재합니다.

1. 소수 판별 방법
2. 누적합

소수를 판별하는 방법은 다음 포스팅에서 확인이 가능합니다.

https://apth1023.tistory.com/73

[Algorithm] 에라토스테네스의 체 (소수 판별)

 

우선 2부터 입력받은 자연수 N까지의 모든 소수를 판별한 이후 해당 소수 값들을 바탕으로 누적합 배열을 만들어주면 됩니다.

 

누적합이란 psum[i] = psum[i - 1] + 현재 값 으로 쉽게 구할 수 있으며, 누적합을 구했다면 2개의 인덱스를 사용해 연속 구간의 합을 체크할 수 있습니다.

 

누적합의 중요한 특징은 다음과 같습니다.

• 원본 배열(arr)의 값 : 1, 2, 3, 4, 5
• 누적합(psum)의 값 : 1, 3, 6, 10, 15
• 위와 같은 상황에서 psum[4] - psum[1]은 12이 되는데 이 값은 arr[2] ~ arr[5]까지의 합을 의미합니다.

소수 판별 방법과 누적합의 특성에 대해 알고 있다면 쉽게 풀 수 있는 문제였습니다.

코드

#include <iostream>
#include <vector>

using namespace std;

#define MAX 4000002

int num;
bool temp[MAX];
vector<int> psum;
int res;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> num;

    // 소수 연산
    for (int i = 2; i <= num; i++)
    {
        for (int j = i + i; j <= num; j += i)
        {
            temp[j] = true;
        }
    }

    // 누적합 연산
    // * 초기값
    int idx = 0;
    psum.push_back(0);

    for (int i = 2; i <= num; i++)
    {
        // 소수가 아닌 경우 건너 뛰기
        if (temp[i] == true) continue;

        // 이전 값 + 현재 값 저장
        psum.push_back(psum[idx] + i);
        idx++;
    }

    int left = 0;
    int right = 1;

    while (left < psum.size() && right < psum.size() && left <= right)
    {
        int tempNum = psum[right] - psum[left];

        // 계산 결과가 결과값보다 작은 경우 오른쪽 인덱스 증가
        if (tempNum < num) right++;
        // 계산 결과가 결과값보다 큰 경우 왼쪽 인덱스 증가
        else if (tempNum > num) left++;
        // 계산 결과가 결과값이랑 같은 경우 최종 경우의 수 증가시키고 오른쪽 증가
        else if (tempNum == num)
        {
            res++;
            right++;
        }
    }

    cout << res;
}