[BOJ 15907 // C++] Acka의 리듬 세상

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 15907번 문제인 Acka의 리듬 세상이다.
문제는 아래 링크를 확인하자.

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

15907번: Acka의 리듬 세상

N개의 수를 어떤 수 K로 나눈 나머지에 따라 분류했을 때, 가장 많은 수가 분류된 나머지를 갖는 수의 개수를 X라 하자.

주어진 N개의 수가 모두 다르다는 조건에 의해, 조사해봐야 하는 K의 값의 범위는 200만까지가 아닌 200만/X 까지가 됨을 계산해낼 수 있다.

 

또한 K=2인 경우 X의 값은 N과 비례하게 나오므로, 나머지를 조사할 필요가 있는 쌍의 개수는 O((200만/X) * N) = O(200만)이 된다. 이는 문제를 해결하기에 충분한 시간복잡도이다.

 

K가 합성수인 경우 K의 소인수를 이용한 분해를 더 잘게 쪼갠 결과만을 얻게 되므로 조사할 필요가 없다는 점을 이용하여, K가 소수인 경우만을 탐색하는 최적화를 추가할 수도 있다.

 

아래는 제출한 소스코드이다.

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

int arr[1000];
vector<bool> sieve(2000001);
int chk[2000001];
short cnt[2000001];

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

	for (int i = 2; i < 1414; i++) {
		if (sieve[i]) continue;
		for (int j = i * i; j < 2000001; j += i) {
			sieve[j] = 1;
		}
	}

	int N; cin >> N;
	int ans = 0;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		if (x & 1) ans++;
		arr[i] = x;
	}

	ans = max(ans, N - ans);

	for (int k = 3; k <= 2000000 / ans; k++) {
		if (sieve[k]) continue;
		for (int i = 0; i < N; i++) {
			int num = arr[i] % k;
			if (chk[num] == k) {
				cnt[num]++;
				if (cnt[num] > ans) ans = cnt[num];
			}
			else {
				chk[num] = k;
				cnt[num] = 1;
			}
		}
	}

	cout << ans;
}