[백준 14572번] 스터디 그룹 (Python3)

import sys
def input(): return [*map(int,sys.stdin.readline().split())]

def update(i,v,x):
  global kn,un,cnt
  cnt += x
  for k in study[i][1]:
    if known[k]==v:
      kn += x
    known[k] += x
  for k in study[i][2]:
    if unknown[k]==v:
      un += x
    unknown[k] += x

def solve():
  j = result = 0
  for i in range(N):
    for j in range(j,N):
      if study[i][0]-study[j][0]<=D:
        break
      update(j,1,-1)
    update(i,0,1)
    result = max(result,cnt*(kn+un-K))
  return result

N,K,D = input()
study = [0]*N
for i in range(N):
  study[i] = [input()[1],input(),0]
  study[i][2] = [*{*range(1,K+1)}-{*study[i][1]}]
study.sort()
known = [0]*(K+1); unknown = [0]*(K+1)
cnt = kn = un = 0
print(solve())

간단한 그리디 알고리즘 문제

 

수식을 살짝 변형시키면, "효율성 E = (그룹내 학생들이 아는 모든 알고리즘의 수+그룹내 학생들이 모르는 모든 알고리즘의 수-알고리즘의 수)*그룹원의 수" 로 정리할 수 있는데, 알고리즘의 수는 상수이고, 나머지 변수들은 그룹원의 수가 증가할수록 커지게 된다.

따라서 실력차이 D를 고려하면 그리디하게 스터디그룹에 최대한 많은 인원을 넣어야 효율성이 최대가 되며, 이는 정렬과 투포인터로 쉽게 해결할 수 있다.

 

풀이를 설명하면,

1. 각 학생들이 아는 알고리즘과 모르는 알고리즘을 정리하고, 학생들의 실력에 따라 정렬한다.

2. known과 unknown 체크리스트를 만든다. 각 리스트에는 해당 문제를 아는 학생들의 수와 모르는 학생들의 수를 기록한다.

3. 투포인터 알고리즘으로 학생들을 그룹에 넣고, D를 벗어나는 학생은 그룹에서 뺀다. 그 과정에서 known, unknown 리스트를 기록하고, 각 값이 0에서 1이 되거나, 1에서 0이 되는 경우 kn(그룹내 학생들이 아는 알고리즘의 수), un(그룹내 학생들이 모르는 알고리즘의 수) 변수를 갱신한다. 또 cnt(그룹내 인원수)도 갱신한다.

4. (kn+un-K)*cnt로 result를 갱신한다.

5. result를 출력한다.

 

 

오늘의 교훈) 그리디하게 해결할 수 있는지를 항상 고려하자