[1644 번] 소수의 연속합

www.acmicpc.net/problem/1644

1644번: 소수의 연속합

 

• N보다 작은 소수를 시간제한 내에 빠르게 구하는 방법이 중요했던 투포인터 문제입니다.

 

[N 보다 작은 소수를 구하는 방법]

1부터 N사이의 수 각각이 자기 자신과 1 외의 다른 수와 나눠 떨어지지 않아야 소수의 정의를 만족합니다.

모든 수에 대해서 직접 확인을 하는 방식은 (N ≤ 4,000,000) 이라는 조건을 고려하면 적절한 방식이 아닙니다.(시간초과)

따라서 해당 문제에서 에라토스테네스의 체를 이용해서 소수를 구했습니다.

	for (int i = 2; i <= n; i++) {
		for (int j = 2; i * j <= n; j++) {
			p[i * j] = false;
		}
	}


	for (int i = 2; i <= n; i++) {
		if (p[i] == true) {
			prime.push_back(i);
		}
	}

첫 번째 for문을 통해서 n 보다 작은 수 각각에 대해 boolean형으로 소수이면 true를 소수가 아니면 false를 저장합니다.

두 번째 for문을 사용해서 소수인 숫자만 vector에 순서대로 저장합니다.

 

다음은 vector에 저장된 소수들을 바탕으로 투포인터를 이용해 조건에 부합하는 부분배열의 수를 count합니다.

	int cnt = 0;
	int left = 0;
	int right = 0;
	int sum = prime.front();

	while (1) {

		if (right == prime_size) break;

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

	}

left right 두 포인터를 이용해서 조건( sum == n )에 부합하는지 확인합니다.