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

문제: 1644번: 소수의 연속합

basic-algo-lecture/workbook/0x14.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x14.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>

using namespace std;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    vector<bool> nums(n + 1, true); // 0 번 인덱스 안써여
    nums[0] = false;
    nums[1] = false;

    for (int i = 2; i < n + 1; i++) {
        // i 의 배수들 모두 제거행..

        for (int j = i * 2; j < n + 1; j += i) {
            nums[j] = false;
        }
    }
    vector<int> primeNums;
    for (int i = 2; i < n + 1; i++) {
        if (nums[i]) {
            primeNums.push_back(i); // 소수만 넣어
        }
    }

    int st = 0;
    int en = 0;
    int len = primeNums.size();
    int ans = 0;
    int tmpSum = 0;
    while (en < len) {
        tmpSum += primeNums[en];
        en++;

        while (tmpSum >= n) {
            if (tmpSum == n) {
                ans++;
            }

            tmpSum -= primeNums[st];
            st++;
        }
    }
    cout << ans;

    return 0;
}

 

일단 에라토스테네스의 체를 이용해서 n 까지 범위의 소수를 모두 찾았다.

 

찾은 소수를 따로 담을 primeNums 벡터를 선언했다. 여기부터는 기존 투포인터 문제 푸는 방식대로 해결하면 된다.

 

일단 문제에서 원하는 건 연속하는 소수들을 더해서 n 이 되면 ans 값에 +1 을 해주는 것.

 

위와 같이 구현하기 위해서 일단 en 이 n 보다 작을때까지 while 문을 돌도록 했다. 매번 while 문마다 tmpSum 에 primeNums[en] 의 값을 더한 후 en 의 값을 증가시켰다. tmpSum 의 값이 n 보다 작으면 소수를 더 더해줘야 하기 때문!

 

만약 tmpSum 의 값이 n 보다 크거나 같다면? 이제 tmpSum 에서 primeNums[st] 값을 뺀 후 st 의 값을 1 증가시켰다.