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

이 문제는 각 학교마다 학생이 본선에 진출할 수 있도록 하는 사람의 최댓값을 출력하도록 하는 문제이다.

 

이때 학교의 수는 200,000 이고 학생의 수는 최대 MAX = 2,000,000 이 주어진다.

 

본선에 진출할 수 있는 학생의 수를 x 라고 한다면 x 의 배수가 되도록 하는 학교의 학생수를 전부 counting 하고 이 때 두 팀 이상이 본선에 참가할 수 있다는 것을 고려해줘야 한다.

 

그렇다면 처음에 각 학교마다 학생의 수 a 를 받을 때 a 명이 전체 학교에서 몇명인지에 대해서 알기 위해 stu_Count 배열을 사용하였다.

 

그리고 에라스토테네스의 체 방법을 이용하여 O(MAX * log(MAX)) 만큼 시간이 소요된다.

 

위에서 말한것처럼 본선 진출 가능한 학생의 수를 x 라고 할 때, 학생 수가 x 의 배수가 되는 학교의 수를 counting 하고 2 이상일 경우 (x * 학교수) 값이 본선에 참가하는 사람의 수가 되는데 이를 모든 경우를 확인하는 과정에서 최댓값을 찾으면 된다. 

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

ll stu_Count[2000001];

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

	ll n, x, MAX=0;
	cin>>n;
	for(int i=0; i<n; i++) {
		cin>>x;
		stu_Count[x]++;
		MAX = max(MAX, x);
	}

	ll res=0, cnt, tmp;
	for(ll i=1; i<=MAX; i++) {
		cnt = stu_Count[i];
		tmp = i*stu_Count[i];

		for(ll j=i+i; j<=MAX; j+=i) {
			if(stu_Count[j]) {
				tmp += i*stu_Count[j];
				cnt += stu_Count[j];
			}
		}

		if(cnt>=2) res=max(res, tmp);
	}

	cout<<res;

	return 0;
}