백준 1644(소수의 연속합)

https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

겨울에 스터디하면서 서강대 raararaara님에게 배운 문제. 그치만 강의가 좋다고만 생각했지, 백준 문제 풀 생각은 전혀 안 했었다. 그러다가 오늘 친구가 풀어보라길래 그때 생각이 나서 강의록을 참조하였다. 

 

이 문제는 부분합 문제이다. 부분합 문제는 여러가지 알고리즘이 있는데 이렇게 정렬된, 연속한 합을 구할 때는 투포인터가 압도적인 알고리즘이라고 알고 있다.

 

엄청 직관적인 알고리즘이다. 

 

어떤 N값을 연속된 소수의 합으로 만들 수 있는가 문제인데, 

 

오름차순 정렬된 수의 나열에서 연속합으로 N을 만드는건 두 개의 포인터로 만약에 작으면 더하고, 크면 빼고 이걸 반복하는 것이다. 

 

int r = 0;
	num = 0;
	for (int l = 0; l < cnt; l++) {
		if (r == cnt) break;
		while (num + v[r] <= N && r < cnt) {
			num += v[r++];
		}
		if (num == N) {
			result++;
		}
		num -= v[l];
	}

이 코드의 시간복잡도는 O(N^2)인데, Amortized analysis에 의해서 극단적인 별로 안되는 경우에만 N^2이고 웬만하면 O(N)의 시간복잡도를 가져서 선형시간복잡도라고 봐도 무방하다고 한다. 

 

소수는 에라토스테네스의 체 알고리즘으로 소수를 빠르게 구할 수 있었다. 

 

이 알고리즘을 처음 써보고, 해서 이 알고리즘이 도대체 어디에 또 쓰일 수 있는지 모르겠다. 

 

문제를 많이 풀어보고 나중에 연관지어서 설명하겠다.

#include<iostream>
#include<vector>
using namespace std;
#define MAX 4000001

int N, cnt = 0, result = 0, num;
vector<int> v(MAX);
bool prime[MAX] = { false };

void solve() {
	int r = 0;
	num = 0;
	for (int l = 0; l < cnt; l++) {
		if (r == cnt) break;
		while (num + v[r] <= N && r < cnt) {
			num += v[r++];
		}
		if (num == N) {
			result++;
		}
		num -= v[l];
	}
}

void init() {
	for (int i = 2; i < MAX; i++) {
        int mul = 2;
		if (prime[i]) continue;
        while(i*mul < MAX){
            prime[i*mul] = true;
            mul++;
        }
    }
}

int main() {
	cin >> N;
	init();

	for (int i = 2; i < MAX; i++) {
		if (!prime[i]) v[cnt++] = i;
	}
	solve();
	cout << result << "\n";
}