[Algorithm] C++ 백준 14572번 : 스터디 그룹

알고리즘 문제를 풀다 보면 다양한 조건을 만족하면서 최대 혹은 최소 값을 구하는 문제가 자주 등장한다. 이번에 살펴볼 문제는 백준 온라인 저지의 14572번 “스터디 그룹"이다. 이 문제는 주어진 조건 하에서 스터디 그룹의 효율성을 최대화하는 그룹을 찾는 것이다.

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

문제 설명

신입생 현우는 알고리즘 공부가 정말 재미있어서 스터디 그룹을 만들어 더욱 열심히 공부하려고 한다. 하지만 그룹에 참여하는 학생이 너무 많으면 효율이 떨어질 것을 우려하여 아래와 같은 조건을 내걸었다.

조건 1: 그룹 내에서 가장 잘하는 학생과 가장 못하는 학생의 실력 차이가 \( D \) 이하이어야 한다.
조건 2: 그룹의 효율성 \( E \)는 다음과 같이 정의된다.
\( E = (\text{그룹 내의 학생들이 아는 모든 알고리즘의 수} - \text{그룹 내의 모든 학생들이 아는 알고리즘의 수}) \times \text{그룹원의 수} \)

현우는 각 학생들의 실력을 수치화하고, 중요한 알고리즘 \( K \)개에 대해 각 학생들이 어떤 알고리즘을 알고 있는지 조사하였다. 이때, 위의 두 가지 조건을 만족하는 학생들의 부분집합 중 효율성이 최대가 되는 그룹을 찾아야 한다.

입력 조건:

첫 줄에 학생의 수 \( N \), 알고리즘의 수 \( K \), 그리고 실력 차이의 최대값 \( D \)가 주어진다. \( (1 \leq N \leq 10^5, 1 \leq K \leq 30, 0 \leq D \leq 10^9) \).
다음 \( N \)개의 줄에는 각 학생에 대한 정보가 주어진다.
- 각 줄은 먼저 해당 학생이 알고 있는 알고리즘의 수 \( M \)과 실력 \( d \)가 주어진다. \( (0 \leq M \leq K, 0 \leq d \leq 10^9) \).
- 다음 줄에 \( M \)개의 정수로 해당 학생이 알고 있는 알고리즘 번호 \( A_i \)가 주어진다. \( (1 \leq A_i \leq K) \).

출력 조건:

조건을 만족하는 그룹 중 효율성이 최대가 되는 그룹의 효율성을 출력한다.

접근 방식

이 문제는 두 가지 주요한 조건을 만족하면서 효율성을 최대화해야 하므로, 효율적인 알고리즘이 필요하다. 우선, 학생들의 실력 차이가 \( D \) 이하인 그룹을 찾아야 하므로, 실력 기준으로 학생들을 정렬하고 슬라이딩 윈도우를 사용하여 조건을 만족하는 그룹을 찾을 수 있다.

또한, 알고리즘의 수 \( K \)가 최대 30이므로 각 학생의 알고리즘 목록은 32비트 정수 하나의 비트마스크로도 표현할 수 있고, 비트마스크의 합집합·교집합은 \( O(1) \)이다. 그러나 슬라이딩 윈도우에서는 학생이 윈도우를 떠날 때 “다른 학생이 아직 이 알고리즘을 아는가"를 알아야 하는데, 비트 OR로 합친 값에서는 한 학생만 빼낼 수 없다. 그래서 알고리즘별로 아는 학생 수를 세는 카운트 배열을 쓴다. 카운트가 0에서 1이 되는 순간과 1에서 0이 되는 순간이 곧 합집합 크기가 변하는 순간이다.

왜 슬라이딩 윈도우가 맞는가. 실력순으로 정렬하면 실력 차이 조건을 만족하는 그룹은 정렬된 배열의 연속 구간으로 한정해도 손해가 없다. 구간 안에서 학생을 하나 더 넣으면 아는 알고리즘의 합집합은 줄지 않고 교집합은 늘지 않으며 그룹원 수는 늘기 때문에, 오른쪽 끝을 고정했을 때 \( D \) 조건을 만족하는 가장 왼쪽 시작점(가장 넓은 구간)이 \( E \)를 최대로 만든다. 따라서 각 오른쪽 끝마다 가장 넓은 구간 하나만 보면 된다. 오른쪽 끝이 커질수록 허용되는 가장 왼쪽 시작점도 줄지 않으므로 두 포인터는 한 방향으로만 움직인다.

따라서, 다음과 같은 전략을 사용한다.

학생들을 실력 기준으로 정렬한다.
투 포인터를 사용하여 슬라이딩 윈도우를 확장하고 축소하면서 실력 차이가 \( D \) 이하인 그룹을 찾는다.
현재 윈도우 내의 학생들이 알고 있는 알고리즘을 관리하기 위해 카운트 배열을 사용한다.
- 각 알고리즘에 대해 현재 윈도우에서 알고 있는 학생 수를 저장한다.
그룹의 효율성 \( E \)를 계산하기 위해 다음을 유지한다.
- total_known: 현재 그룹에서 알고 있는 모든 알고리즘의 수 (중복 제거).
- total_known_by_all: 현재 그룹의 모든 학생이 알고 있는 알고리즘의 수.
윈도우를 이동할 때마다 \( E \)를 계산하고 최대값을 갱신한다.

이러한 접근 방식의 시간 복잡도는 정렬 \( O(N \log N) \), 윈도우 이동 중 카운트 갱신 \( O(NK) \), 오른쪽 끝마다 \( K \)개를 훑는 total_known_by_all 재계산 \( O(NK) \)을 합한 \( O(N \log N + NK) \)다. \( N = 10^5 \), \( K = 30 \)이면 약 \( 3 \times 10^6 \)번 연산이라 제한 시간 안에 충분하다. 공간 복잡도는 학생별 알고리즘 목록을 저장하는 \( O(NK) \)다.

구분	복잡도
정렬	\( O(N \log N) \)
윈도우 이동과 카운트 갱신	\( O(NK) \)
`total_known_by_all` 재계산	\( O(NK) \)
전체 시간	\( O(N \log N + NK) \)
공간	\( O(NK) \)

다른 접근과의 비교. 오른쪽 끝마다 이분탐색으로 시작점을 찾을 수도 있지만, 어차피 구간의 카운트를 다시 만들어야 하므로 투 포인터보다 나을 것이 없다. 부분집합을 전부 열거하는 완전탐색은 \( 2^N \)이라 불가능하다. 구간 안에서 “모든 학생이 아는 알고리즘"을 비트 AND 누적으로 구하려 하면 학생이 빠질 때 되돌릴 수 없어 같은 이유로 카운트 배열이 필요하다.

C++ 코드와 설명

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Student {
    int skill;                // 학생의 실력
    vector<int> algorithms;   // 학생이 알고 있는 알고리즘 목록
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    long long D;
    cin >> N >> K >> D;

    vector<Student> students(N);

    // 학생 정보 입력
    for (int i = 0; i < N; ++i) {
        int M;
        cin >> M >> students[i].skill;
        students[i].algorithms.resize(M);
        for (int j = 0; j < M; ++j) {
            cin >> students[i].algorithms[j];
            --students[i].algorithms[j]; // 알고리즘 번호를 0부터 시작하도록 조정
        }
    }

    // 학생들을 실력 기준으로 정렬
    sort(students.begin(), students.end(), [](const Student &a, const Student &b) {
        return a.skill < b.skill;
    });

    vector<int> algorithm_counts(K, 0); // 각 알고리즘을 알고 있는 학생 수
    int total_known = 0;                // 그룹에서 알고 있는 알고리즘의 총 수
    int total_known_by_all = 0;         // 그룹의 모든 학생이 알고 있는 알고리즘의 수
    int left = 0;                       // 슬라이딩 윈도우의 왼쪽 포인터
    int group_size = 0;                 // 현재 그룹의 크기
    long long max_E = 0;                // 최대 효율성

    // 오른쪽 포인터를 이동하며 슬라이딩 윈도우 확장
    for (int right = 0; right < N; ++right) {
        group_size++; // 그룹 크기 증가

        // 새로운 학생의 알고리즘 정보를 업데이트
        for (int alg : students[right].algorithms) {
            if (algorithm_counts[alg] == 0) {
                total_known++; // 새로운 알고리즘 발견
            }
            algorithm_counts[alg]++;
        }

        // 실력 차이가 D를 초과하면 왼쪽 포인터 이동하여 윈도우 축소
        while (students[right].skill - students[left].skill > D) {
            // 왼쪽 학생의 알고리즘 정보를 업데이트
            for (int alg : students[left].algorithms) {
                algorithm_counts[alg]--;
                if (algorithm_counts[alg] == 0) {
                    total_known--; // 알고리즘을 아는 학생이 더 이상 없음
                }
            }
            group_size--; // 그룹 크기 감소
            left++;
        }

        // total_known_by_all을 재계산
        total_known_by_all = 0;
        for (int alg = 0; alg < K; ++alg) {
            if (algorithm_counts[alg] == group_size) {
                total_known_by_all++; // 모든 학생이 알고 있는 알고리즘
            }
        }

        // 현재 그룹의 효율성 계산
        long long E = (total_known - total_known_by_all) * group_size;
        if (E > max_E) {
            max_E = E; // 최대 효율성 갱신
        }
    }

    cout << max_E << '\n'; // 결과 출력

    return 0;
}

코드 설명

입력 단계에서는 알고리즘 번호를 1부터가 아니라 0부터 시작하도록 줄여 저장해 algorithm_counts의 인덱스로 바로 쓰고, 학생을 실력 기준으로 정렬해 연속 구간이 곧 후보 그룹이 되도록 준비한다.

탐색 단계에서는 오른쪽 포인터 right를 한 칸씩 옮기며 학생을 그룹에 넣는다. 새 학생이 아는 알고리즘마다 algorithm_counts를 1 올리고, 그 값이 0에서 1이 되면 그룹이 처음 아는 알고리즘이므로 total_known을 1 올린다. 이어서 right와 left의 실력 차이가 \( D \)를 넘는 동안 left의 학생을 빼는데, 이때 그 학생이 아는 알고리즘의 카운트를 1 내리고 0이 되면 그룹에서 사라진 알고리즘이므로 total_known을 1 내린다.

계산 단계에서는 algorithm_counts[alg]가 현재 group_size와 같은 알고리즘의 수를 세어 total_known_by_all을 구한다. 카운트가 그룹 크기와 같다는 것은 그룹의 모든 학생이 그 알고리즘을 안다는 뜻이다. 그다음 \( E \)를 계산해 최댓값을 갱신한다. 윈도우 안에 학생이 한 명뿐이면 total_known과 total_known_by_all이 같아 \( E = 0 \)이 된다.

작은 예로 \( D = 1 \)이고 정렬된 실력이 1, 2, 4인 세 학생이 각각 {1}, {1, 2}, {3}을 안다고 하자.

right	윈도우(실력)	total_known	total_known_by_all	group_size	E
0	[1]	1	1	1	0
1	[1, 2]	2	1	2	2
2	[4] (실력 1, 2를 제거)	1	1	1	0

right = 2에서 실력 4와 1의 차이 3, 4와 2의 차이 2가 모두 \( D \)를 넘어 left가 두 칸 이동한다. 최댓값은 2다.

결론

이 문제의 핵심은 실력순 정렬 위의 슬라이딩 윈도우에서 알고리즘별 카운트 배열로 합집합 크기를 O(1)에 갱신하는 것이다.

학습 목표와 흔한 오개념

이 글을 읽고 나면 다음을 할 수 있다.

실력순 정렬 후 연속 구간만 봐도 되는 이유를 합집합·교집합의 단조성으로 설명한다.
비트마스크 대신 카운트 배열이 필요한 상황을 구분한다.
total_known과 total_known_by_all의 갱신 시점을 윈도우 이동 과정에서 추적한다.

오개념 1: 비트 OR로 합친 마스크에서 학생을 빼면 된다. 학생 A={1}, B={1}을 OR로 합치면 {1}인데, A가 윈도우를 떠날 때 비트 1을 끌 수 없다. B가 아직 알기 때문이다. 이 반례가 있어서 “아는 학생 수"를 세는 카운트 배열이 필요하다.

오개념 2: 답이 32비트를 넘으니 long long이 필수다. 이 문제의 E는 최대 약 \( 3 \times 10^6 \)이라 int로도 담긴다. long long은 필수가 아니라 안전한 습관이다.

코너 케이스 및 실수 포인트

케이스	설명	처리 방법
학생 1명	N=1이면 윈도우에 한 명뿐이라 \( E = 0 \)	`max_E` 초기값 0이 그대로 출력된다
D = 0	실력이 정확히 같은 학생끼리만 그룹이 된다	`> D` 비교라 실력이 같으면 윈도우가 유지된다
실력이 같은 학생 다수	정렬 후 인접하므로 한 윈도우에 모두 들어간다	정렬 기준이 `skill` 하나여도 결과에 영향이 없다
M = 0인 학생	알고리즘을 하나도 모르면 `total_known_by_all`이 0이 된다	반복문이 돌지 않아 카운트 변화가 없고, 그룹 크기만 늘어난다
전원이 같은 알고리즘만 아는 경우	`total_known`과 `total_known_by_all`이 같아 \( E = 0 \)	답이 0일 수 있으므로 `max_E`를 0으로 시작한다
곱셈 오버플로우	\( E \le K \times N \approx 3 \times 10^6 \)이라 `int`로도 충분하다	곱셈 습관상 `long long`을 쓰되, 실력 \( d \)와 \( D \)의 뺄셈(최대 \( 10^9 \))이 `int` 범위 안인지도 확인한다