[백준/1222] 홍준 프로그래밍 대회 (Python)

Problem : https://www.acmicpc.net/problem/1222

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

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 00:23:56

 

---

 

문제 설명

 

 

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

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

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

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

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

 

 

입력 및 출력

 

입력

 

첫째 줄에 홍준이의 대회에 참여 의사를 밝힌 학교의 수 N (2 ≤ N ≤ 200,000)이 주어진다.
둘째 줄에는 각 학교 학생의 수가 주어진다. 학생의 수는 구간 [1, 2,000,000]에 포함된다.

 

출력

 

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

 

입력 예시

 

3
1 2 4

 

출력 예시

 

4

 

 

---

 

풀이

 

면접 준비에 포스팅은 못하고 문제만 풀어놨다가... 오늘에서야 비로소 문제 풀이와 함께 포스팅하게 되었다.

 

어떤 대학이 프로그래밍 대회에 참여할 수 있으려면, 팀 인원이 그 대학의 학생 수의 약수일 때만 가능하다. 즉 전략을 다르게 생각하여, 모든 대학들의 약수의 경우를 카운트하도록 해보자. 모든 대학에 대해 시행한다면, 최대 O(N * sqrt(S))로 줄일 수 있다. (S는 최대 학생 수이다.) 카운터 등을 이용하여 시행한다면 더더욱 시간 효율적으로 접근할 수 있다.

 

모든 과정을 시행하면, 저장된 카운트는 본 대회에 참여 가능한 대학의 수를 의미한다. 모든 대학은 한 팀만이 본선에 참여 가능하므로, 총 참여 가능한 학생의 수는 (참여하는 대학) * (팀원 수)가 된다. 이 경우의 수를 따지는 데에는 O(S)의 시간복잡도가 소요되며, 이 중 최댓값을 출력하기만 하면 된다.

 

 

풀이 코드(pypy3)

from collections import Counter

N = int(input())
student_dict = Counter(map(int, input().split()))
maxval = max(student_dict.keys())
divisor = [0]*(maxval+1)

for key, val in student_dict.items() :
  for n in range(1, int(key ** 0.5) + 1) :
    if key % n == 0 :
      divisor[n] += val
      if key // n != n :
        divisor[key // n] += val

ans = 0
for i in range(1, maxval+1) :
  if divisor[i] > 1 :
    ans = max(ans, divisor[i]*i)
print(ans)

 

풀이 완료!