#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;structStudent{intskill;// 학생의 실력
vector<int>algorithms;// 학생이 알고 있는 알고리즘 목록
};intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);intN,K;longlongD;cin>>N>>K>>D;vector<Student>students(N);// 학생 정보 입력
for(inti=0;i<N;++i){intM;cin>>M>>students[i].skill;students[i].algorithms.resize(M);for(intj=0;j<M;++j){cin>>students[i].algorithms[j];--students[i].algorithms[j];// 알고리즘 번호를 0부터 시작하도록 조정
}}// 학생들을 실력 기준으로 정렬
sort(students.begin(),students.end(),[](constStudent&a,constStudent&b){returna.skill<b.skill;});vector<int>algorithm_counts(K,0);// 각 알고리즘을 알고 있는 학생 수
inttotal_known=0;// 그룹에서 알고 있는 알고리즘의 총 수
inttotal_known_by_all=0;// 그룹의 모든 학생이 알고 있는 알고리즘의 수
intleft=0;// 슬라이딩 윈도우의 왼쪽 포인터
intgroup_size=0;// 현재 그룹의 크기
longlongmax_E=0;// 최대 효율성
// 오른쪽 포인터를 이동하며 슬라이딩 윈도우 확장
for(intright=0;right<N;++right){group_size++;// 그룹 크기 증가
// 새로운 학생의 알고리즘 정보를 업데이트
for(intalg:students[right].algorithms){if(algorithm_counts[alg]==0){total_known++;// 새로운 알고리즘 발견
}algorithm_counts[alg]++;}// 실력 차이가 D를 초과하면 왼쪽 포인터 이동하여 윈도우 축소
while(students[right].skill-students[left].skill>D){// 왼쪽 학생의 알고리즘 정보를 업데이트
for(intalg:students[left].algorithms){algorithm_counts[alg]--;if(algorithm_counts[alg]==0){total_known--;// 알고리즘을 아는 학생이 더 이상 없음
}}group_size--;// 그룹 크기 감소
left++;}// total_known_by_all을 재계산
total_known_by_all=0;for(intalg=0;alg<K;++alg){if(algorithm_counts[alg]==group_size){total_known_by_all++;// 모든 학생이 알고 있는 알고리즘
}}// 현재 그룹의 효율성 계산
longlongE=(total_known-total_known_by_all)*group_size;if(E>max_E){max_E=E;// 최대 효율성 갱신
}}cout<<max_E<<'\n';// 결과 출력
return0;}
코드 설명
학생 정보 입력 및 전처리:
각 학생의 알고리즘 목록을 입력받고, 알고리즘 번호를 0부터 시작하도록 조정한다.
학생들을 실력 기준으로 정렬하여 슬라이딩 윈도우를 사용할 수 있도록 준비한다.
슬라이딩 윈도우를 사용한 그룹 탐색:
오른쪽 포인터 right를 이동하면서 그룹에 학생을 추가한다.
새로운 학생의 알고리즘을 algorithm_counts에 반영하고, 새로운 알고리즘을 발견하면 total_known을 증가시킨다.
실력 차이가 D를 초과하면 왼쪽 포인터 left를 이동하여 그룹에서 학생을 제거한다.
그룹에서 제거된 학생의 알고리즘을 algorithm_counts에서 감소시키고, 알고리즘을 아는 학생이 없으면 total_known을 감소시킨다.
효율성 계산 및 최대값 갱신:
total_known_by_all을 각 알고리즘에 대해 그룹의 모든 학생이 알고 있는지 확인하여 계산한다.
현재 그룹의 효율성 E를 계산하고, 최대값을 갱신한다.
결론
이 문제는 슬라이딩 윈도우와 투 포인터 기법을 사용하여 효율적으로 해결할 수 있었다. 알고리즘의 수가 적다는 점을 이용하여 각 알고리즘의 카운트를 배열로 관리함으로써 시간 복잡도를 O(NK)로 줄일 수 있었다. 문제를 풀면서 슬라이딩 윈도우를 적용하는 방법과 카운트를 효율적으로 관리하는 방법에 대해 다시 한 번 생각해볼 수 있었다.
추가적으로, 알고리즘 번호를 0부터 시작하도록 조정하여 배열 인덱싱을 간단하게 만들었다. 이러한 작은 최적화가 전체 코드의 가독성과 효율성을 높이는 데 도움이 된다.
이번 문제를 통해 투 포인터와 슬라이딩 윈도우 기법이 다양한 상황에서 활용될 수 있음을 알게 되었으며, 앞으로도 이러한 기법을 적절히 활용하여 문제를 효율적으로 해결할 수 있도록 노력해야겠다.