취미로 코딩하기

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

이번에 볼 문제는 백준 1222번 문제인 홍준 프로그래밍이다.
문제는 아래 링크를 확인하자.

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

처음에 문제를 "예선에 참가하는 사람을 최대화"하는 문제로 잘못 이해하고 풀었었다. 이후 문제를 제대로 이해한 뒤에도 잘못된 가정을 찾아내는 데에 시간이 많이 걸려 고생한 문제이다.

이 문제에서 구해야하는 것은 "본선에 참가하는 사람을 최대화(단, 팀은 둘 이상이 있어야 함)"하는 것이다.

이를 구하기 위해서는 1 이상 200만 이하의 각 수 K에 대하여 (K * (학생 수가 K의 배수인 학교의 수))의 최댓값을 구하면 된다.

각 학교의 학생수를 소인수분해하고, 그 결과를 이용해 모든 소인수를 구해내 학생수가 어떤 수의 배수가 될 수 있는지를 전부 기록하면 문제를 빠르게 해결할 수 있다.

각 수를 소인수분해할 때, 에라토스테네스의 체를 응용한 전처리(소수의 경우 0, 합성수의 경우 1 대신 해당 수를 나누는 가장 작은 소인수를 기록)로 일반적으로 잘 알려진 O(sqrt(N))의 약수 탐색 알고리즘보다 빠르게 모든 약수를 찾아낼 수 있다. (수 하나의 약수를 찾는 것은 O(sqrt(N))이 더 빠르나, 범위가 정해져있고 약수를 찾아야 하는 수가 많다면 위의 방법이 더 빠르다.)

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

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

int sieve[2000001];
ll cnt[2000001];

vector<pair<int, int>> p; // (소인수,cnt)
int psize;
void func(int idx, int val) {
	if (idx == psize) cnt[val]++;
	else {
		int curval = 1, pp = p[idx].first, iterp = p[idx].second;
		for (int i = 0; i <= iterp; i++) {
			func(idx + 1, val * curval);
			curval *= pp;
		}
	}
}


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

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

	int Q; cin >> Q;
	ll total = Q;
	while (Q--) {
		p.clear();
		int N; cin >> N;
		int prev = -1;
		while (N > 1) {
			int tmp = sieve[N];
			if (tmp == prev)p.back().second++;
			else prev = tmp, p.emplace_back(make_pair(tmp, 1));
			N /= tmp;
		}
		psize = p.size();
		func(0, 1);
	}
	
	for (ll i = 2; i < 2000001; i++) {
		if (cnt[i] < 2) continue;
		ll tmp = i * cnt[i];
		if (tmp > total) total = tmp;
	}

	cout << total;
}