[백준/14572] 스터디 그룹 (Python)

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

14572번: 스터디 그룹

 

Difficulty : Platinum 5

 

Status : Solved

 

Time : 00:26:31

 

---

 

문제 설명

 

 

신입생 현우는 알고리즘 공부가 정말 재밌다.

현우는 이번에 스터디 그룹을 만들어 더욱 열심히 공부해보려 한다.

하지만 사공이 많으면 배가 산으로 간다고, 그룹에 참여하는 학생이 너무 많을 경우 지지부진한 결과가 나오게 될 것을 우려한 현우는 아래와 같은 조건을 내걸었다.

 

• 그룹 내에서 가장 잘 하는 학생과 가장 못 하는 학생의 실력 차이가 D 이하여야 한다.

또한, 그룹의 효율성 E를 아래와 같이 정의하였다.

 

• E = (그룹 내의 학생들이 아는 모든 알고리즘의 수 - 그룹 내의 모든 학생들이 아는 알고리즘의 수) * 그룹원의 수

 

현우는 위와 같은 두 가지 조건을 체크하기 위해, 모든 학생들의 실력을 수치화하고, 중요한 알고리즘 K개에 대해, 각 학생들이 어떤 알고리즘을 알고 있는지를 모두 조사하였다.

현우는 조건을 만족하는 학생들의 부분집합 중 효율성이 최대가 되는 그룹을 뽑아 스터디 그룹으로 만들 생각이다.

현우가 만들 스터디 그룹의 효율성은 얼마가 될까?

 

 

입력 및 출력

 

입력

첫 줄에 학생의 수 N, 알고리즘의 수 K, 문제에 설명한 D가 주어진다. (1 ≤ N ≤ 105, 1 ≤ K ≤ 30, 0 ≤ D ≤ 109)

이어 N명의 학생에 대한 정보가 아래와 같이 주어진다.

• M d (0 ≤ M ≤ K, 0 ≤ d ≤ 109): 해당 학생이 알고 있는 알고리즘의 수, 해당 학생의 실력
• 다음 줄에, M개의 정수 Ai: 해당 학생이 알고 있는 알고리즘들 (1 ≤ Ai ≤ K)

 

출력

 

가장 효율성이 높은 그룹의 효율성을 출력한다.

 

입력 예시

 

3 3 10
1 20
1
1 10
2
1 0
3

 

출력 예시

 

4

 

 

---

 

풀이

 

우선, 가장 잘 하는 학생과 가장 못 하는 학생들의 실력차가 D이하여야 한다는 조건이 있으므로, 정렬을 이용해 다음과 같이 생각해 볼 수 있다.

 

• 실력차에 따라 정렬을 수행한다.
• 그리고 정렬 내 모든 조건을 만족하는 구간 (l, r)에 대해(즉 실력[r] - 실력[l] <= D), 효율성 E를 구하여 최댓값을 구해보자.

즉 우리는 l, r 두 개의 포인터를 가지고 그리디하게 탐색을 수행하면 된다. 이 방법은 또 한가지 이점이 있는데, 학생들이 아는 알고리즘의 수를 카운팅할 때 업데이트하는 방식으로 저렴하게 구할 수 있다는 장점이 있다. 

 

또한, 우리는 효율성 E를 세 가지 팩터 a, b, c로 치환하여, E = (a - b) * c로 나타낼 수 있다. 여기서

 

• a : 그룹원의 수가 많아지면 증가 (기존 그룹이 모르는 알고리즘 추가)하거나 유지(기존 그룹이 알던 알고리즘)
• b : 그룹원의 수가 많아지면 감소 (기존 그룹이 모르는 알고리즘 추가)하거나 유지(기존 그룹 모두가 알던 알고리즘)
• c : 그룹원의 수가 많아지면 증가

하며, a, c는 E와 양의 상관관계, b는 음의 상관관계를 가짐을 알 수 있다. 따라서 최대한 조건 내에 그룹원이 많이 포함되도록 포인터를 조정하면 더욱 빠르게 문제를 풀 수 있다.

 

 

풀이 코드

from collections import defaultdict
import sys
input = sys.stdin.readline

N, K, D = map(int, input().split())
algo_dict = defaultdict(int)
student_list = list()

for _ in range(N) :
  M, d = map(int, input().split())
  student_list.append([d] + list(map(int, input().split())))

student_list.sort()
ans = 0
l, r = 0, 0
while r < N :
  for algo in student_list[r][1:] :
    algo_dict[algo] += 1
  r += 1
  while l < r and student_list[r-1][0] - student_list[l][0] > D :
    for algo in student_list[l][1:] :
      algo_dict[algo] -= 1
      if not algo_dict[algo] :
        del algo_dict[algo]
    l += 1
  algo_len = len(algo_dict.keys())
  E = (algo_len - list(algo_dict.values()).count(r-l)) * (r - l)
  ans = max(ans, E)

print(ans)

풀이 완료!