[백준] 1222번: 홍준 프로그래밍 대회 - C++

문제

홍준이는 프로그래밍 대회를 개최했다. 이 대회는 사람들이 팀을 이루어서 참가해야 하며, 팀원의 수는 홍준이가 정해준다. 팀원이 홍준이가 정한 값보다 부족하다면, 그 팀은 대회에 참여할 수 없다. 모든 팀은 같은 수의 팀원으로 이루어져 있다.

대회에 참여 의사를 밝힌 학교는 총 N개이다. 각 학교는 모든 학생이 참여할 수 있는 경우에만 대회에 참가한다. 즉, 남는 사람 없이 모든 학생이 팀에 들어갈 수 있어야 한다.

대회는 예선과 본선으로 구성되어 있다. 모든 팀은 같은 학교 소속으로 이루어져 있어야 한다. 예선에서 각 학교 1등팀만 본선에 진출한다. 

홍준이의 대회는 올해가 첫 해이기 때문에, 많은 관심이 필요하다. 따라서, 본선에 참가하는 사람의 수를 최대가 되도록 팀원의 수를 정하려고 한다. 또, 본선이 지루해지는 것을 막기 위해 적어도 두 팀이 본선에 참가할 수 있어야 한다.

홍준이가 팀원을 몇 명으로 정해야 본선에 참가하는 사람의 수가 최대가 되는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 홍준이의 대회에 참여 의사를 밝힌 학교의 수 N (2 ≤ N ≤ 200,000)이 주어진다.

둘째 줄에는 각 학교 학생의 수가 주어진다. 학생의 수는 구간 [1, 2,000,000]에 포함된다.

 

출력

첫째 줄에 홍준이의 대회 본선에 참가하는 사람의 수의 최댓값을 출력한다.

---

말도 어렵고 조건도 많고 여러모로 문제 이해부터 힘들었다ㅠㅠ

출력되는 수는 본선에 참가하는 팀의 수나 한 팀당 인원수가 아닌 사람의 총 인원수이다. 본선에 참가하는 팀은 모두 같은 수의 팀원을 가져야 되고, 본선에 진출하는 학교에서는 남는 사람 없이 모든 학생이 팀에 들어갈 수 있어야 한다.

즉, 예선에 참가한 학교의 학생 수 사이에서 약수를 찾고 거기서 가장 많은 인원수가 참여할 수 있는 경우를 골라야 하는 문제이다.

 

long long int team = 0;
for(int i = 1; i <= maximum; i++) {
    long long int count = 0;
    for(int j = 0; j < N; j++) {
        if(school[j] % i == 0) {
            count += i;
        }
    }
    if(count > team) {
        team = count;
    }
}

처음에 이런식으로 생각을 했는데, 숫자의 범위를 보아하니 딱봐도 시간초과가 날것같아 제출 시도조차 안해보고 그냥 시간복잡도를 줄일 수 있는 방법을 찾아봤었다..

 

처음에 값을 받을 때 학교 배열에 학생수를 넣어주는 것이 아니라, 1부터 200만 사이의 학생 수를 배열로 만든 뒤 인덱스 만큼의 인원이 참여하는 학교의 수를 세주는 방식으로 푸는 방법이 있더라....

for(int i = 1; i <= MAX; i++) {
    long long int count = 0;
    for(int j = 1; j * i <= MAX; j++) {
        count += school[i * j];
    }
    if(count < 2) continue;
    team = max(team, count * i);
}

그 외에 기본적인 아이디어는 같았다. 예선에 참여하는 학교가 두 팀일 경우 두 팀 모두 올라가야 되기 때문에 두 수간 최대공약수만 구해준 뒤 넘어가고, 다른 경우에 계속 최댓값을 비교해주며 i * j만큼의 인원수가 참여하는 학교를 계속 세주어 팀원수 * 학교 수와 기존의 최댓값을 비교해준 뒤, 마지막 최댓값을 출력해준다.

 

당연히 2000000 * 200000을 감안하여 자료형은 long long int로 설정해주기

 

코드

#include <cstdio>
#define MAX 2000001

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

int school[MAX] = { 0 };

int main(void) {
    int N;
    scanf("%d", &N);

    for(int i = 0; i < N; i++) {
        int temp;
        scanf("%d", &temp);
        school[temp]++;
    }

    long long int team = 0;
    for(int i = 1; i <= MAX; i++) {
        long long int count = 0;
        for(int j = 1; j * i <= MAX; j++) {
            count += school[i * j];
        }
        if(count < 2) continue;
        team = max(team, count * i);
    }

    printf("%lld\n", team);
    return 0;
}