백준 - 1644 소수의 연속합

해결과정 - 에라스토테니스의 체, 투포인트

시간안에 해결하려면 소수를 미리 구해놔야 된다는 생각이 들어 에라스토테니스의 체를 이용하게 되었다. 그리고 항상 연속이라는 의미가 보이면 슬라이딩 윈도우기법이나 투포인터를 떠올리는데 이는 외쪽 오른쪽 둘다 값이 다르게 변하므로 투포인터를 이용하여 해결하였다.

 

결론은 단순이 이러한 알고리즘을 알고있느냐 라는 문제였다

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <stack>
#include <cmath>
#include <unordered_map>

#define FAST ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

typedef long long ll;

using namespace std;

//에라스토테네스의 채
vector<int> prime;

int main() {
    FAST;
    int n;
    cin >> n;

    vector<int> visited(n + 1, 0);

    for (int i = 2; i <= n; i++) {
           if (!visited[i]) {
                prime.push_back(i);
                int j = 1;
                while (i * j <= n) {
                    visited[i * j] = 1;
                    j++;
                }
           }
    }

    int left = 0, right = 0, sum = 0, cnt = 0;

    while (right < prime.size()) {
        sum += prime[right];

        if (sum < n) {
        }
        else if (sum == n) {
            cnt++;
            sum -= prime[left];
            left++;
        }
        else {
            while (sum > n) {
				sum -= prime[left];
				left++;
			}
            if (sum == n) {
				cnt++;
                sum -= prime[left];
                left++;
			}
        }

        right++;
    }

    cout << cnt << "\n";

    return 0;
}

 

후기

게임 제작해야되는데 몸이 아파서 단순한 문제만 풀수 있어서 너무 슬프다