[백준/BOJ] 14572 스터디 그룹 (c++)

[백준/BOJ] 14572 스터디 그룹 (c++)

14572번: 스터디 그룹

2025.03.10 - [Competitive Programming] - 15. 투 포인터 (Two pointers method, c++)

15. 투 포인터 (Two pointers method, c++)

---

10000명의 학생이 있습니다. 학생들의 부분 집합(Subset)을 구해서 그 중 가장 효율성이 높은 그룹을 찾는 문제입니다.

 

모든 부분 집합을 구하는 것은 O(2^N)이 걸리므로 불가능합니다.

 

문제의 조건에 스터디그룹이 결성 되려면 그룹 내에서 가장 잘하는 학생과 가장 못하는 학생의 실력차가 D 이하여야 합니다.

 

학생의 실력 차이 오름차순으로 정렬을 한뒤 투포인터를 통해 실력차 내에서 이루어질 수 있는 그룹을 탐색한다면 O(N)에 문제를 해결할 수 있습니다.

 

효율성은 그룹 내의 학생들이 아는 총 알고리즘 수와, 그룹 내의 모든 학생들이 아는 알고리즘 수, 그룹원의 수로 계산됩니다.

 

a는 학생의 인덱스번호(i)와 능력치를 담고 능력치 오름차순으로 정렬을 하기위한 vector 입니다.

 

z는 i번째 학생이 알고있는 알고리즘 목록을 저장하는 vector입니다.

 

k는 현재 그룹에 속한 학생들이 알고있는 알고리즘의 개수를 세는 vector입니다. 이를 통해 그룹원의 수와 비교를 하면 총 알고리즘 수, 모든 학생이 아는 알고리즘 수를 계산할 수 있습니다.

 

투포인터는 두개의 포인터 모두 맨 왼쪽에서 시작해 오른쪽으로 이동하며 left~right 구간의 학생이 현재 그룹에 있다는 것을 의미합니다.

 

만약 현재 구간의 실력차이가 D 보다 크다면 left를 이동시켜 실력차이를 줄입니다. 그렇지 않은 경우 효율성을 계산 후 right를 이동시켜 새로운 그룹을 탐색합니다.

---

#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, e) for (int i=s; i<e; i++)
int N, K, D;
vector<pair<int, int>> a;
vector<vector<int>> z(100001);
vector<int> k(31);

bool compare(const pair<int, int>& a, const pair<int, int>& b) {
    return a.second < b.second;
}
int eff(int len) {
    int total = 0, all = 0;
    REP(i, 1, K+1) {
        if (k[i]) {
            total++;
            if (k[i] == len) all++;
        }
    }
    return (total-all)*len;
}
int solve() {
    sort(a.begin(), a.end(), compare);
    int left = 0;
    int right = 0;
    for (auto x: z[a[0].first]) {
        k[x]++;
    }
    int ans = 0;
    while (left <= right && right < N) {
        if ((a[right].second - a[left].second) > D) {
            for (auto x: z[a[left++].first]) {
                k[x]--;
            }
            continue;
        }
        ans = max(ans, eff(right-left+1));
        right++;
        if (right < N) {
            for (auto x: z[a[right].first]) {
                k[x]++;
            }
        }
    }
    cout << ans;
    return 0;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> K >> D;
    int m, d, x;
    REP(i, 0, N) {
        cin >> m >> d;
        a.push_back({i, d});
        REP(j, 0, m) {
            cin >> x;
            z[i].push_back(x);
        }
    }
    solve();
    return 0;
}