BOJ 14572 : 스터디 그룹

14572번: 스터디 그룹 (acmicpc.net)

14572번: 스터디 그룹

 

이 문제는 그리디 + 투 포인터로 풀 수 있다.

 

 

 

임의의 그룹원 집합 알파에 대해 "그룹 내에서 가장 잘 하는 학생과 가장 못 하는 학생의 실력 차이가 D 이하여야 한다." 가 성립하는 그룹원 A 를 더한 집합이, 집합 알파보다 항상 효율성이 크므로, 이 로직으로 풀 수 있다.

그냥 하면 시간초과가 나니, 정렬과 투포인터를 사용해 O(NK) 에 풀 수 있다.

 

난이도(개인적): Platinum IV

난이도(객관적): Platinum V

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define pp pair<int, vector<int> > 

int N, K, D;
vector<pp> students;
int A[31];

bool cmp(pp left, pp right) {
    return left.first < right.first;
}

int main() {
    
    cin >> N >> K >> D;

    for (int i = 0; i < N; i++) {
        int M, d; cin >> M >> d;

        vector<int> algorithms;

        for (int i = 0; i < M; i++) {

            int Ai; cin >> Ai;
            algorithms.push_back(Ai);

        }

        students.push_back({ d, algorithms });
    }

    sort(students.begin(), students.end(), cmp);

    int l = 0; int r = 0; int ans = 0;
    while (r < N) {

        int Md = students[r].first;
        int md = students[l].first;

        for (int i = 0; i < students[r].second.size(); i++) {
            A[students[r].second[i]]++;
        }

        while (md + D < Md) {

            for (int i = 0; i < students[l].second.size(); i++) {
                A[students[l].second[i]]--;
            }

            l++; md = students[l].first;
        }
        
        int p2 = 0; int p1 = 0;
        for (int i = 1; i <= K; i++) {
            if (A[i] == r - l + 1) { p2++; p1++; } else if (A[i] != 0) { p1++; }
        }
        
        ans = max(ans, (p1 - p2) * (r - l + 1));

        r++;
    }

    cout << ans << endl;
}