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를 출력한다.
오늘의 교훈) 그리디하게 해결할 수 있는지를 항상 고려하자