[G5] 백준 34558번 Prime Median C++ 에라토스테네스의 체, 누적 합, 이분 탐색

리뷰

 

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

닫힌 구간에서의 소수 중앙값을 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• p : 소수 여부를 저장할 배열
• pre : 구간의 소수 개수를 저장할 누적합 배열

 

함수

없음

 

 

문제풀이

• 2~1,000,000까지의 소수를 구해 배열 p를 초기화한다.
• 2~1,000,000까지의 누적합을 구해 배열 pre를 초기화한다.
• 변수 n을 초기화 하고, 값을 입력 받은 후 n개의 쿼리를 수행한다.
• 매 쿼리마다 변수 a, b에 닫힌 구간을 입력 받아준다.
• 변수 cnt에 pre[b]-pre[a-1]을 통해 a~b구간에서의 소수 개수를 저장한다.
• 만약 cnt가 홀수인 경우 이분 탐색을 통해 소수의 중앙값을 찾아 출력 후 개행문자를 삽입한다.
• 만약 cnt가 짝수인 경우 -1을 출력 후 개행문자를 삽입한다.

 

트러블 슈팅

1. 이분 탐색 내에서 l을 증가시키는 분기 처리에 부등호를 추가하여 WA를 받았다.
2. sum이 (cnt+1)/2보다 작은 경우에만 오른쪽으로, 크거나 같은 경우 왼쪽으로 이동시켜 AC를 받았다.

 

참고 사항

1. 소수가 아닌 경우 p배열의 값을 true, 소수인 경우 p배열의 값을 false로 초기화 해주었다.
2. 따라서 누적합을 구할 때 p[i]가 false인 경우 1을 증가해 주었다.

 

정답 코드

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

const int N = 1e6 + 1;
bool p[N];
int pre[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	for (int i = 2; i * i < N; ++i) {
		if (p[i]) continue;
		//cout << i << " " << p[i] << "\n";
		for (int j = i * i; j < N; j += i) p[j] = true;
	}

	for (int i = 2; i < N; ++i) pre[i] = pre[i - 1] + (p[i] ? 0 : 1);

	int n; cin >> n;
	while (n--) {
		int a, b; cin >> a >> b;
		int cnt = pre[b] - pre[a - 1];
		//cout << cnt << "\n";

		if (cnt % 2) {
			int l = a, r = b;

			while (l <= r) {
				int mid = (l + r) / 2;
				int sum = pre[mid] - pre[a - 1];

				if (sum == (cnt + 1) / 2 && !p[mid]) {
					cout << mid << "\n";
					break;
				}
				else if (sum < (cnt + 1) / 2) l = mid + 1;
				else r = mid - 1;
			}
		}
		else cout << -1 << "\n";
	}
}