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

문제

난이도 : 골드 3
백준 1644번 : 소수의 연속합

코드

#include <bits/stdc++.h>

using namespace std;

int N;
bool arr[4000004];
vector<int> v;

void Func()
{
    for (int i = 2; i <= N; i++)
    {
        for (int j = i * 2; j <= N; j += i)
        {
            if (arr[j]) continue;
            arr[j] = true;
        }
    }
}

int main()
{
    cin >> N;

    Func();

    for (int i = 2; i <= N; i++)
    {
        if (!arr[i]) v.push_back(i);
    }

    int answer = 0;
    int sum = 0;

    for (int i = (int)v.size() - 1; i >= 0; i--)
    {
        int idx = i;

        while (idx >= 0 && sum < N)
        {
            sum += v[idx--];
        }

        if (sum == N)
        {
            answer++;
        }

        sum = 0;
    }

    cout << answer;

    return 0;
}

풀이

우선 N까지의 소수를 벡터에 담기 위해 arr 배열으로 에라토스테네스의 체를 이용해 소수를 판별하는 배열을 만들었다. 모르면 구글에 많은 자료가 있으니 찾아보길!!
N까지의 소수를 벡터에 담은 후 벡터에서 제일 큰 수부터 더해가며 N이 완성되는지 볼 것이다.
벡터 v의 인덱스인 i는 그대로 두고 idx라는 인덱스 변수를 하나 더 선언해 벡터의 idx번째부터 그 전 인덱스를 연속해가며 더해 만약 sum이 N보다 같거나 크게 되면 while문을 빠져나올 것임(이때 idx가 벡터 v의 범위를 벗어나지 않게 하기 위해 예외 처리가 필요!)
while문을 나와서 만약 sum이 N과 같다면 경우의 수를 하나 증가시킨다. N보다 크다면 그냥 지나간다. 그리고 sum을 초기화하는 것 잊지말기.

결과