[G3] 백준 1644번 소수의 연속합 C++ 투 포인터, 에라토스테네스의 체

리뷰

 

https://www.acmicpc.net/workbook/view/8709

주어진 값까지의 모든 소수를 구하고, 해당 소수 배열에서의 연속합이 주어진값과 일치하는 경우의 수의 개수를 구하는 문제

 

 

전역 변수

• n : 일치 시켜야 하는 정수를 저장할 변수
• ans : 소수의 연속합이 n값과 같은 케이스의 개수를 저장할 변수
• sosu : 에라토스테네스의 체를 사용하여 각 정수가 소수인지 여부를 저장할 정수형 배열, 크기는 400만 초과

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, n까지의 수 중 소수가 아닌 경우 sosu배열에 1로 표시해 준다.
2. 정수형 타입 벡터 sosus를 초기화 하고, 2 ~ n까지의 수에서 sosu배열 상 값이 0인 경우 추가해 준다.
3. 포인터로 사용할 정수형 변수 l, r을 각각 0으로 초기화 해준다.
4. 현재 l포인터 ~ r포인터의 값의 합을 나타낼 정수형 변수 sum을 0으로 초기화 해준다.
5. 탐색 최대 범위를 지정할 정수형 변수 len에 sosus의 size를 저장해 준다.
6. l이 r보다 작거나 같고, r이 len보다 작다면 while을 통해 계속 반복문을 실행해 준다.
7. 만약 sum + sosus[r]이 n보다 작을 경우 sum에 sosus[r]을 더해주고 r을 증가시켜 준다.
8. sum + sosus[r]이 n보다 클 경우 sum에 sosus[l]을 빼주고 l을 증가시켜 준다.
9. sum + sosus[r]이 n과 동일할 경우 ans를 증가시키고 sum에 sosus[l]을 빼주고 l을 증가시켜 준다.
10. 탐색이 종료된 후에 ans에 저장된 값을 출력해주면 된다.

 

참고 사항

없음

 

 

정답 코드

#include<iostream>
#include<vector>
#include<cstring>
#include<cmath>
using namespace std;

int n, ans;
int sosu[4000001];

int main() {
	cin >> n;
	for (int i = 2; i <= pow(n, (double)1/2); i++) {
		if (sosu[i]) continue;
		for (int j = i + i; j <= n; j += i) {
			sosu[j] = 1;
		}
	}

	vector<int> sosus;
	for (int i = 2; i <= n; i++) {
		if (!sosu[i]) sosus.push_back(i);
	}

	int l = 0, r = 0, sum = 0, len = sosus.size();
	while (l <= r && r < len) {
		if (sum + sosus[r] < n) {
			sum += sosus[r];
			r++;
		}
		else if (sum + sosus[r] > n) {
			sum -= sosus[l];
			l++;
		}
		else {
			ans++;
			sum -= sosus[l];
			l++;
		}
	}
	cout << ans;
}