[BOJ 14572] 스터디 그룹

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

14572번: 스터디 그룹

 

- 문제 요약

 

현우는 이번에 스터디 그룹을 만들어 더욱 열심히 공부해보려 한다. 현우의 스터디 그룹에는 다음과 같은 조건이 있다.

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

 

그룹의 효율성 E는 다음과 같이 정의된다.

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

 

현우가 만들 스터디 그룹의 효율성을 구해 출력하세요.

 

 

- 알고리즘 정리

 

E의 식에서 "그룹 내의 학생들이 아는 모든 알고리즘의 수"를 A, "그룹 내의 모든 학생들이 아는 알고리즘의 수"를 B라고 정의해 보겠습니다.

A는 비트 연산에서 OR에 해당하고, B는 AND에 해당합니다.

A는 증가, B는 감소하는 형태를 보이고 있으므로(같은 경우도 존재), 학생들의 능력치를 기준으로 정렬한 다음 투포인터 알고리즘을 돌려주면 AC를 받을 수 있습니다.

 

 

- 코드 정리

 

#include<bits/stdc++.h>
using namespace std;

struct st{
	int a,b;
}stu[100001];
int n,k,d,result,l,r,co[31];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>k>>d;
	for(int i=0;i<n;i++){
		int c;
		cin>>c>>stu[i].b;
		while(c--){
			int a;
			cin>>a;
			a--;
			stu[i].a|=(1<<a);
		}
	}
	sort(stu,stu+n,[](const st &i,const st &j){return i.b<j.b;});
	while(r<n){
		int w=0;
		while(stu[r].b-stu[l].b>d){
			for(int i=0;i<k;i++){
				if(stu[l].a&(1<<i)){
					co[i]--;
				}
			}
			l++;
		}
		for(int i=0;i<k;i++){
			if(stu[r].a&(1<<i)){
				co[i]++;
			}
		}
		for(int i=0;i<k;i++){
			if(co[i]>0&&co[i]<r-l+1){
				w++;
			}
		}
		result=max(result,w*(r-l+1));
		r++;
	}
	cout<<result; 
}

코드 제출 결과