BOJ 1644 : 소수의 연속합

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/1644

 

 

N이 4,000,000으로 매우 크므로, 매번 소수를 판단하는 것은 비효율적이다.

따라서, 소수의 판단은 에라토스테네스의 체를 이용한다.

int N;
int prime[4000000 + 50000];
int primeSet[4000000 + 50000];
int pcnt;

void eratos()
{
	prime[1] = 1;
	for (int i = 2; i * i <= 4000000; i++)
	{
		if (!prime[i])
		{
			for (int k = i * i; k <= 4000000; k += i)
				prime[k] = 1;
		}
	}
}

 

1 ~ 4,000,000 사이에 만들어진 에라토스테네스의 체를 보고 소수만 primeSet에 모은다.

int main(void)
{
	int hptr, lptr, sum, cnt;

	eratos();

	scanf("%d", &N);

	for (int i = 2; i <= N; i++)
		if (!prime[i]) primeSet[pcnt++] = i;
        
    ...
 
 
	return 0;
}

---

이제 문제의 예시 41이 소수의 연속합으로 나타낼 수 있는 경우가 3인지 확인해보자.

 

1) 소수를 연속해서 더한 값 sum이 41보다 작으면 high pointer(high)를 올려서 계속해서 더해나간다.

2) 더한 값 sum이 41보다 커지면 low pointer(low)를 올려서 값을 뺀다.

3) 41이 된다면 count한다.

 

그림으로 한 번 확인해보자.

처음에 h와 l은 primeSet에서 0을 가르키고 있다.

찾아야할 값은 41이고, sum과 cnt는 초기에 모두 0이다.

 

sum이 0(< 41)이므로 h를 올려가며 primeSet에 있는 소수를 더해간다.

primeSet[h] = 2이므로 sum은 2가 되고, h = 1로 이동한다.

 

여전히 sum이 41보다 작으므로 다음 primeSet[h]를 더하고 h를 증가시킨다.

 

계속해서 더해나가면 13까지 더했을 때, sum이 41이 된다.

41이 되는 소수의 연속합을 찾았으므로 cnt를 증가시킨다.

 

41은 41보다 작지 않으므로, primeSet[l]의 값을 sum에서 뺀다. 그리고 l을 증가시킨다.

sum은 39가 된다.

 

다시 sum이 41보다 작아졌으므로 primeSet[h]를 더하고 h를 증가시킨다.

sum은 56이 된다.

 

sum이 41보다 작지 않으므로, primeSet[l]을 빼고 l을 증가시킨다.

sum은 48이 된다.

 

48은 41보다 작지 않으므로, primeSet[l]을 빼고 l을 증가시킨다.

sum이 41이 되었으므로, cnt를 증가시킨다.

 

계속해서 h와 l을 증가시키면 최종적으로 아래와 같이 소수의 연속합이 되는 41을 찾을 수 있게 된다. 

따라서 정답은 cnt = 3이 된다.

 

최종 코드는 아래를 참고하자.

#include <stdio.h>

int N;
int prime[4000000 + 50000];
int primeSet[4000000 + 50000];
int pcnt;

void eratos()
{
	prime[1] = 1;
	for (int i = 2; i * i <= 4000000; i++)
	{
		if (!prime[i])
		{
			for (int k = i * i; k <= 4000000; k += i)
				prime[k] = 1;
		}
	}
}

int main(void)
{
	int high, low, sum, cnt;

	eratos();

	scanf("%d", &N);

	for (int i = 2; i <= N; i++)
		if (!prime[i]) primeSet[pcnt++] = i;

	high = low = sum = cnt = 0;
	while (1)
	{
		if (high > pcnt) break;

		if (sum == N) cnt++; /* N을 찾았으므로 count */

		if (sum < N) sum += primeSet[high++]; /* N보다 작으면 더해준다. */
		else sum -= primeSet[low++]; /* N과 같거나 작으면 뺀다. */
	}

	printf("%d\n", cnt);

	return 0;
}

 

two pointer를 이용하여 소수의 연속합

 

sum = primeSet[l] + primeSet[l + 1] + ... + primeSet[h-1];

 

을 O(1)의 연산으로 계속 유지시키기 때문에 빠르게 답을 찾는다.