[Baekjoon] 홍준 프로그래밍 대회(BOJ 1222)

👀 문제 설명

문제

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

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

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

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

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

 

입력

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

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

 

출력

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

 

예제 입력 1

3

1 2 4

 

예제 출력 1

4

 

예제 입력 2

2

1 5

 

예제 출력 2

2

 

예제 입력 3

5

4 6 3 8 9

 

예제 출력 3

9

 

✍🏻풀이

이 문제는 약수를 사용하는 문제이다.

예제3을 보면, 

프로그래밍 대회에 참가하는 학교는 5개이고, 각 학교는 4, 6, 3, 8, 9명의 학생을 갖고 있다.

홍준이가 정한 팀원의 수 student라고 하자.

1) student = 4인 경우,

4명의 학생을 보유한 학교와

8명의 학생을 보유한 학교가 참가할 수 있다. 이 때 본선에 진출하는 학생수는 8명이 된다.

2) student = 6인 경우,

6명의 학생수를 보유한 학교만 참여할 수 있으므로 불가능하다.

3) student = 3인 경우,

6명의 학생을 보유한 학교와

3명을 보유한 학교,

9명을 보유한 학교가 참여할 수 있다. 이 때 본선에 진출하는 학생수는 9명이 된다.

4) student = 8인 경우,

8명을 보유한 학교만 참여할 수 있으므로 불가능하다.

5) student = 9인 경우,

9명을 보유한 학교만 참여할 수 있으므로 불가능하다.

본선에 진출하는 학생수의 최댓값은 9명이므로 답은 9가 된다.

 

문제를 보고 벡터를 써야겠다는 생각이 제일 처음 들었다.

먼저, 학교의 수 N과 각 학교의 학생수를 저장하는 vector<int> studentNumber를 선언했다.

그리고 for문으로 벡터에 접근, 각 인자의 result 값을 구했다.

for문을 두 번 사용하여 studentNumber[i]값을 약수로 갖는 값들이 몇 개인지 구했다. 이 값 * studentNumber[i]를 해서 답을 구했는데, timeout이 났다..! 검색해보니 이 문제는 벡터로 풀면 timeout이 발생하는듯 했다.

 

아래는 timeout이 발생한 코드이다.

//
//  BOJ_1222.cpp
//  Algorithm
//
//  Created by 조수민 on 2020/07/23.
//  Copyright © 2020 조수민. All rights reserved.
//
//  홍준 프로그래밍 대회(https://www.acmicpc.net/problem/1222)

#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

int N; // 대회에 참가하는 학교의 수
vector<int> studentNumber; // 각 학교의 학생 수 벡터
// 이 문제는 벡터로 풀면 메모리가 터진다..!

void input()
{
    
    cin >> N;
    studentNumber.resize(N);
    
    for (int i = 0; i < N; i++)
        cin >> studentNumber[i];
}

int getMaxNum()
{
    int max = 0; // 본선에 참가할 수 있는 사람의 수의 최댓값
    
    // 벡터를 두 번 접근 -> 시간복잡도가 n의 제곱근 -> timeout이 난다.
    for (int i = 0; i < studentNumber.size(); i++)
    {
        int schoolNum = 0;
        int currentNum = studentNumber[i]; // 홍준이가 정한 팀원의 수
        
        // 벡터를 다시 접근하여 currentNum으로 나누어 떨어지는 학교의 수가 몇인지 센다.
        for (int j = 0; j < studentNumber.size(); j++)
        {
            if (studentNumber[j] % currentNum == 0)
                schoolNum += 1;
        }
        
        // 학교의 수가 1이라면 continue로 건너뛴다. (적어도 두 팀이 본선에 참가해야 하기 때문)
        if (schoolNum == 1)
            continue;
        
        int current = schoolNum * currentNum; // current는 currentNum이 studentNumber[i]일 때, 본선에 참가하는 사람의 수이다.
        
        if (max < current) // max보다 current값이 크다면
            max = current; // max를 current값으로 바꿔준다.
    }
    
    return max;
}

int main()
{
    input();
    
    cout << getMaxNum() << endl;
    
    return 0;
}

---

벡터대신 배열을 사용해보았다.

schoolArray 배열을 사용했다. schoolArray[number]에 값을 저장하는 식으로 사용했다. 이 때, number는 학생수가 number인 학교가 몇 개인지 저장하는 역할을 한다.

즉, schoolArray[5] = 3이라면 학생수가 5명인 학교가 3개라는 뜻이다.

이후 for문을 사용하여 schoolArray[i] + schoolArray[2 * i] + schoolArray[3 * i] + ... 을 구한다.

즉, i를 약수로 갖는 값들이 몇 개인지 구하는 것이다.

이 수 * i를 이전에 구한 값과 비교해 더 큰 값을 저장해나가면 된다.

 

상수 선언

#define MAX 2000000

 

필요한 변수

int N : 대회에 참가하는 학교의 수 

long long schoolArray[MAX + 1] : 학생수가 i인 학교가 몇개인지 저장하는 배열. ex) schoolArray[5] = 3일 경우, 학생수가 5명인 학교가 3곳이다.

 

알고리즘

위의 설명과 같다.

 

코드

//
//  BOJ_1222.cpp
//  Algorithm
//
//  Created by 조수민 on 2020/07/23.
//  Copyright © 2020 조수민. All rights reserved.
//
//  홍준 프로그래밍 대회(https://www.acmicpc.net/problem/1222)

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

#define MAX 2000000

int N; // 대회에 참가하는 학교의 수
long long schoolArray[MAX + 1];

void input()
{
    
    cin >> N;
    
    for (int i = 0; i < N; i++)
    {
        int number;
        cin >> number;
        schoolArray[number]++;
    }
}

long getMaxNum()
{
    long maxNum = 0;
    
    for (int i = 1; i <= MAX; i++)
    {
        int count = 0; // 참가하는 학교의 수
        
        /**
         schoolArray[i] + schoolArray[2 * i] + schoolArray[3 * i] + ... 를 구할 수 있다.
         즉, i를 약수로 갖는 값들이 몇 개인지 알 수 있다.
         */
        for (int j = i; j <= MAX; j += i)
            count += schoolArray[j];
        
        if (count < 2) // 본선에는 적어도 2팀이 참가해야 한다.
            continue;
        
        maxNum = max(maxNum, (long)count * (long) i); // 학생수 = 각 팀을 구성하는 학생 수 * 대회 참여가 가능한 학교 수
    }
    
    return maxNum;
}

int main()
{
    input();
    
    cout << getMaxNum() << endl;
    
    return 0;
}

 

[참고] m.blog.naver.com/PostView.nhn?blogId=schezang&logNo=220941061427&proxyReferer=https:%2F%2Fwww.google.com%2F