백준 1644 소수의 연속합

소수의 값으로만 부분 집합을 구해서 연속합을 구하는 문제이다. 부분 집합의 연속합을 구하는 부분에서 당연히 투포인터가 쓰일 것이고 어떻게 소수 모음을 만들어 내는지가 중요한 포인트이다. 

 

필자는 두달전에 한번 풀었고 다시 복습을 통해 풀었는데 소수를 구하는 방법히 전혀 달랐다. 그래서 안좋은 예와 좋은 예 두 코드를 작성해보겠습니다. 

 

안좋은 예

에스트라네스의 체를 활용했는데 상당히 비효율적으로 코드가 작성되었다. 2부터 400000만까지 소수인지 확인하며 하나씩 추가해줬습니다.

#include <cstdio>
#include <math.h>

int arr[4000002];

int setPrimeNumber(int num);
int discoverCount(int N);

int main(){
	int index = 0, N;
	for(int sub = 2; sub <= 4000000; sub++){
		if(setPrimeNumber(sub)){
			arr[index] = sub;
			index++;
		}
	}

	scanf("%d", &N);

	printf("%d", discoverCount(N));
}

int setPrimeNumber(int num){

	for(int i = 2; i <= sqrt(num); i++){
		if(num%i == 0)
			return 0;
	}
	return 1;
}

int discoverCount(int N){
	int start = 0, end = 0;
	int count = 0, subSum = 0;

	while(end <= N){
		if(subSum < N){
			subSum+=arr[end];
			end++;
		}else if(subSum >= N){
			subSum-=arr[start];
			start++;
		}

		if(N == subSum)
			count++;
	}

	return count;
}

 

좋은 예

위와 다르게 2의 배수의 3의 배수를....4000000까지 소수가 아님을 체크하여 순서대로 넣어줍니다. 2의 경우 2를 제외한 4, 6, 8, 10....

시작 점을 제외하기 위해 밑의 반복문의 시작이 sub + sub인 것이다.

 

#include <cstdio>
#include <math.h>

int isPrime[4000002], arr[4000002];

int setPrimeNumber(int num);
int discoverCount(int N);

int main(){
	int index = 0, N;
	for(int sub = 2; sub <= 4000000; sub++){
		if(isPrime[sub] == 1)continue;
		for(int multiNum = sub + sub; multiNum <= 4000000; multiNum+=sub){
			isPrime[multiNum] = 1;
		}
	}

	for(int sub = 2; sub <= 4000000; sub++){
		if(isPrime[sub] == 0){
			arr[index] = sub;
			index++;
		}
	}

	scanf("%d", &N);

	printf("%d", discoverCount(N));
}

int discoverCount(int N){
	int start = 0, end = 0;
	int count = 0, subSum = 0;

	while(end <= N){
		if(subSum < N){
			subSum+=arr[end];
			end++;
		}else if(subSum >= N){
			subSum-=arr[start];
			start++;
		}

		if(N == subSum)
			count++;
	}

	return count;
}