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

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

난이도: Gold2

카테고리: 정수론

Problem

1. 출전의사가 있는 학교는 모든 인원을 정해진 수로 팀을 꾸려야 출전가능

2. 대회 본선엔 학교당 한 팀만 올라갈 수 있고, 본선엔 최소 2팀은 올라와야함

3. 과연 팀 단위를 몇명으로 해야 본선에 올라오는 인원이 최대가 될까?

Idea

처음엔 각 학교 인원수의 약수를 모두 구해서, 가장 많은 약수 * 학교수를 하면 답이 나오지 않을까?했습니다. 근데,약수를 구하는 것에서 시간초과가 나서 풀이를 조금 참고했는데, 되게 간단하게 풀리는 문제였습니다.

k 배수에 해당하는 학교가 몇개일까?

이렇게 접근하면 N(NlogN)으로 접근이 가능해집니다.

//N까지의 배수를 모두 탐색
for(int i = 1 ; i <=2_000_000;i++ ){
 // 2_000_000 ^ 2 이니까 int를 넘어섬..
	long cnt = 0;
    //배수에 걸리는 학교가 있다면 카운트 업
    for(int j = i ; j <=2_000_000; j += i){
    	cnt += schools[j];
    }
    if(cnt > 1){
         max = Math.max(max,cnt * i);
    }
}

배수 구하는것이 N(logN)인 이유

지피티 피셜,

Solution

package week28_Math;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_1222_G2_홍준프로그래밍대회_김태수 {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] schools = new int[2_000_001];

        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        //학교의 사이즈들을 저장
        for(int i = 0 ; i <N ;i++){
            int idx = Integer.parseInt(st.nextToken());
            schools[idx]++;
        }

        long max = 0;

        // 배수에 해당되는 학교가 몇개인지 확인하면 되지 않을까?
        // 2배수 몇개, 3배수 몇개,.. 그리고 그 갯수 * 배수 하면 본선 인원수
        // 갯수가 2 이상인 것들중 최댓값을 출력
        
        for(int i = 1 ; i <=2_000_000;i++ ){
            // 2_000_000 ^ 2 이니까 int를 넘어섬..
            long cnt = 0;
            for(int j = i ; j <=2_000_000; j += i){
                cnt += schools[j];
            }
            if(cnt > 1){
                max = Math.max(max,cnt * i);
            }
        }

        System.out.println(max);
        
    }
}