[BOJ] 백준 1222 - 홍준 프로그래밍 대회

문제 링크

1222번: 홍준 프로그래밍 대회

첫째 줄에 학교의 수 N(2<= N <= 200,000)을 입력 받고

둘째 줄에 각 학교 학생의 수를 입력 받는다.

학생의 수는 1이상 2,000,000이하이다.

 

이때, 한 학교가 대회에 참가할 수 있다 함은 팀원의 수가 해당 학교의 약수인 경우에 해당한다.

게다가 본선에는 최소 두 팀 이상이 진출해야한다.

 

대회 본선에 참가한 사람의 수는 (본선에 진출한 학교의 수) * (팀원의 수)이다.

본선의 참가한 사람의 수의 최대값을링크

 

불러오는 중입니다...

첫째 줄에 학교의 수 N(2<= N <= 200,000)을 입력 받고

 

둘째 줄에 각 학교 학생의 수를 입력 받는다.

 

학생의 수는 1이상 2,000,000이하이다.

 

 

 

이때, 한 학교가 대회에 참가할 수 있다 함은 팀원의 수가 해당 학교의 약수인 경우에 해당한다.

 

게다가 본선에는 최소 두 팀 이상이 진출해야한다.

 

 

 

대회 본선에 참가한 사람의 수는 (본선에 진출한 학교의 수) * (팀원의 수)이다.

본선의 참가한 사람의 수의 최댓값을 구해야 한다.

 

이때, 본선의 참가한 사람의 수는 최대 2,000,000 * 200,000 = 400,000,000,000 (4000억)이기 때문에

int 자료형은 적절하지 않아보인다.

 

처음에는 divisor 배열을 선언하여 자연수 i를 약수로 가지는 입력이 주어지면

divisor[i]++을 한 후

마지막에 divisor[i]*i 의 최대값만 구하려고 했다.

소스코드는 아래와 같다.

 

#include <iostream>

using namespace std;

long long divisor[2000001];

long long max(long long a, long long b) {
	return a > b ? a : b;
}

void divisorCount(int a) {
	for (long long i = 1; i*i <= a; i++) {
		if (a % i == 0) {
			divisor[i]++;
			if (a != i * i) {
				divisor[a / i]++;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		divisorCount(a);
	}
	long long maxParticipants = 0;
	for (long long i = 1; i <= 2000000; i++) {
		if (divisor[i] < 2) {
			continue;
		}
		else {
			maxParticipants = max(maxParticipants, divisor[i] * i);
		}
	}
	cout << maxParticipants << "\n";
}

 

그러나, 약수를 구하는 과정에서 시간이 오래걸리는 지, 시간 초과가 발생했다.

 

그래서 이번에는 팀원의 수를 먼저 정하고, 해당 팀원의 수의 배수들이 얼마나 있는지 찾기로 했다.

사실 divisor 배열을 그대로 사용하긴 했는데

아래 소스코드에서는 약수가 아닌, 각 학교의 학생 수를 카운트한 것이다.

 

#include <iostream>

using namespace std;

long long divisor[2000001];

long long max(long long a, long long b) {
	return a > b ? a : b;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		divisor[a]++;
	}
	long long maxParticipants = 0;
	for (long long i = 1; i <= 2000000; i++) {
		long long cnt = 0;
		for (long long j = i; j <= 2000000; j += i) {
			cnt += divisor[j];
		}
		if (cnt >= 2) {
			maxParticipants = max(maxParticipants, cnt * i);
		}
	}
	cout << maxParticipants << "\n";
}

 

위 소스코드로 제출했더니 정답이 나왔다.