Logo냥냠감자기술 블로그
Skip to Content
AlgorithmGreedy (14)스터디 그룹
작성일: 2024-01-12

문제

백준 14572 - 스터디 그룹 

  • 난이도: 플레5
  • 알고리즘: 그리디

코드

#include <iostream> #include <vector> #include <algorithm> using namespace std; int getValue(int stdNum, vector<int>& state) { int cnt=0; for(int i=0; i<state.size(); i++) { if(state[i]>0 && state[i]<stdNum) { cnt++; } } return cnt*stdNum; } void setState(vector<pair<int, int>>& stdValue, vector<vector<int>>& stdKnowAlgo, vector<int>& state, int ptr, int flag) { int currPtr=stdValue[ptr].second; for(int i=0; i<stdKnowAlgo[currPtr].size(); i++) { int currAlgoIndex=stdKnowAlgo[currPtr][i]; state[currAlgoIndex]+=flag; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int stdNum, algoNum, availGap; cin>>stdNum>>algoNum>>availGap; vector<pair<int, int>> stdValue(stdNum); vector<vector<int>> stdKnowAlgo(stdNum, vector<int>()); for(int i=0; i<stdNum; i++) { int currKnowAlgoNum; cin>>currKnowAlgoNum>>stdValue[i].first; stdValue[i].second=i; for(int j=0; j<currKnowAlgoNum; j++) { int algoIndex; cin>>algoIndex; stdKnowAlgo[i].push_back(algoIndex-1); } } sort(stdValue.begin(), stdValue.end()); int ret=0; int startPoint=0, endPoint=0; vector<int> state(algoNum, 0); setState(stdValue, stdKnowAlgo, state, 0, 1); while(true) { if(stdValue[endPoint].first-stdValue[startPoint].first>availGap) { setState(stdValue, stdKnowAlgo, state, startPoint, -1); startPoint++; continue; } ret=max(ret, getValue(endPoint-startPoint+1, state)); endPoint++; if(endPoint>=stdNum) break; setState(stdValue, stdKnowAlgo, state, endPoint, 1); } cout<<ret; }

회고

아이디어보다 구현이 조금 더 어려웠던거 같기도 하다. 실력 순서대로 정렬한 후 투 포인터를 이용해 탐색을 할 경우 선형 시간 안에 최적일 수 있는 모든 경우의 수를 탐색할 수 있다. 만약 어떤 한 사람을 포함하기로 한 상황에서 가능한 최대한 많은 스터디원을 모으는 것이 효율성을 최대화 하는데 손해일 수 없다는 것은 쉽게 알 수 있다. 따라서 실력순으로 정렬한 상황에서 투포인터로 가리키는 두 지점 사이에는 start가 가리키는 사람을 포함하는 최대한 많은 스터디원을 가진 상황이 모두 고려된다. 이 상황에서 getValue() 함수를 이용해 효율성을 구한 후, 이를 반복해 최대 효율성을 출력했다. end포인터를 옮기는 상황과 start포인터를 옮기는 상황 모두 현재 그룹이 알고 있는 알고리즘 목록을 갱신할 필요가 있는데, flag를 이용해 한 함수에서 처리하도록 했다.