이 문제는 그리디 + 투 포인터로 풀 수 있다.
임의의 그룹원 집합 알파에 대해 "그룹 내에서 가장 잘 하는 학생과 가장 못 하는 학생의 실력 차이가 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;
}
'Problem Solving > Else' 카테고리의 다른 글
Problem Solving @ 2022/04/18 (0) | 2022.04.19 |
---|---|
BOJ 5419 : 북서풍 (0) | 2022.04.12 |
LIS 문제를 세그먼트 트리를 이용하여 풀이하는 방법 (0) | 2022.04.06 |
BOJ 11570 : 환상의 듀엣 (0) | 2022.04.06 |
BOJ 1509 : 팰린드롬 분할 (0) | 2022.04.05 |