백준 14572 스터디 그룹

조건에 맞는 학생들의 조합을 찾는 문제이다. 각 학생은 3개의 데이터를 가지고 있다. 실력, 알고 있는 알고리즘 수, 알고리즘 종류들.

여기서 데이터 표현을 좀 따져봐야 하는것은 알고리즘 종류이다. 

각 학생별로 최대 30개의 알고리즘을 알 수 있는데, 이걸 Vector로 하나하나 저장하자니 나중에 그룹별로 어떻게 아는지 확인하기에 좋지 않다. 그렇다고 bool 배열 만들자니 뭔가 정신없고. 

나는 이걸 Bitmask로 표현했다. int 형 변수가 32비트니까 30개까지의 알고리즘을 알고/모르고를 전부 표현할 수 있다.

 

그 외에는 투 포인터를 사용해 그룹을 탐색하는것은 똑같다. L, R을 가지고 R을 늘리며 탐색하다가, 조건에 안맞으면 L을 하나 늘리고, 빠진 원소에 대한 연산을 한다.

여기에 더해, 그룹 내 구성원들이 각 알고리즘을 알고 있는 명수를 저장하는 배열 cnt[30] 을 만들어둔다. cnt[i] 는 현재 그룹 사람들 중, i 번째 알고리즘을 알고 있는 사람의 수이다. 이것이 그룹원 수와 동일하면, 그 알고리즘은 그룹원 모두가 아는 알고리즘이 된다. 그렇지 않을 경우 그 알고리즘은 (그룹 내 학생이 아는 모든 알고리즘의 수 - 그룹 내의 모든 학생들이 아는 알고리즘의 수)에 포함된다.

 

탐색은 R이 N 보다 작을동안 계속해서 L과 R을 움직이며 이루어진다. 만약 현재 그룹이 조건에 맞지 않는다면, L을 한칸 움직이고 그 빠진 학생이 아는 알고리즘들을 cnt[] 에서 하나씩 빼준다.

R이 늘어났을때는 반대로 cnt[]에 하나씩 올려준다.

탐색을 하고, cnt[] 배열을 죽 돌면서 0보다 크고(누군가는 알고 있고) 현재 그룹수만큼 알고 있지 않은(다 알고 있지 않은) 알고리즘의 수(그룹 내 학생이 아는 모든 알고리즘의 수 - 그룹 내의 모든 학생들이 아는 알고리즘의 수)를 구한다.

이것을 현재 그룹 수로 곱해주면 효율성이 나오고, 탐색하며 이것의 최대값을 구하면 된다.

---

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

// 구조체 선언. 각 학생들을 저장하는 구조체
// 학생의 실력으로 정렬하기.
// 학생의 실력으로 정렬된 상황에서 D 조건 맞으면 확인?
// 각 학생이 아는 알고리즘은 비트마스킹으로 처리해두기.

int N;
int K;
int D;
int cnt[31];
struct student{
    int skill;
    int algo;
    int algoCnt;
};

// 오름차순 정렬
struct cmp {
    bool operator()(student s1, student s2)
    {
        return s1.skill < s2.skill;
    }
};

int main()
{
    std::cin >> N >> K >> D;
    std::vector<student> stdList;
    for (int i = 0; i < N; ++i)
    {
        student tmp;
        tmp.algo = 0;
        std::cin >> tmp.algoCnt >> tmp.skill;
        for (int j = 0; j < tmp.algoCnt; ++j)
        {
            int algo;
            std::cin >> algo;
            int mask = (1<<(algo - 1));
            tmp.algo = tmp.algo | mask;
        }
        stdList.push_back(tmp);
    }

    // for (student s : stdList){
    //     int algo = s.algo;
    //     for (int i = 1; algo; algo/=2, i++)
    //     {
    //         if (algo & 1)
    //             std::cout << i;
    //     }
    //     std::cout << '\n';
    // }
    std::sort(stdList.begin(), stdList.end(), cmp());
    //  for (student s : stdList){
    //     int algo = s.algo;
    //     for (int i = 1; algo; algo/=2, i++)
    //     {
    //         if (algo & 1)
    //             std::cout << i;
    //     }
    //     std::cout << '\n';
    // }
    int l = 0;
    int r = 0;
    int maxEff = 0;
    // while (l <= r && l < N)
    // {
    //     if (r < N && stdList[l].skill - stdList[r].skill <= D)
    //     {
    //         int len = r - l + 1;
    //         int All = INT_MAX;
    //         int AllCnt  = 0;
    //         int Sum = 0;
    //         int SumCnt = 0;
    //         // std::cout << "skill diff "<< stdList[l].skill << " - "  <<  stdList[r].skill << "<= D" << '\n';
    //         for (int i = 0 ; i < len; ++i)
    //         {
    //             All = All & stdList[l + i].algo;
    //             Sum = Sum | stdList[l + i].algo;
    //         }
    //         while (All)
    //         {
    //             if (All & 1)
    //                 AllCnt++;
    //             All /= 2;
    //         }
    //         while (Sum)
    //         {
    //             if (Sum & 1)
    //                 SumCnt++;
    //             Sum /= 2;
    //         }
    //         int eff = (SumCnt - AllCnt) * len;
    //         maxEff = std::max(eff, maxEff);
    //         r++;
    //     } 
    //     else
    //     {
    //         l++;
    //         // r = l;
    //     }
    // }


// 현재 그룹에서 알고 있는 알고리즘을 저장하는 배열 cnt => cnt[i] = 현재 그룹에서 i 번째 알고리즘을 알고 있는 사람 수.

    while (r < N)
    {
        int cur = 0;
        while (stdList[r].skill - stdList[l].skill > D)
        {
            // 만약 스킬 차이가 D보다 크게 되면, l번째 학생이 알고 있는것은 cnt에서 빼주기.
            for (int i = 0; i < K; i++)
                if (stdList[l].algo & (1 << i))
                    cnt[i]--;
            l++;
        }
        for (int i = 0; i < K; i++)
            if (stdList[r].algo & (1<< i))
                cnt[i]++;
        // 모든 사람이 모든 알고리즘을 알고 있으면 cur = 0. 누구 하나라도 알고 있지만, 모두 알고 있지 않은 경우 cur ++
        for (int i = 0; i < K; i++)
            if (cnt[i] > 0 && cnt[i] < r - l + 1)
                cur++;
        maxEff = std::max(maxEff, cur * (r - l + 1));
        r++;
        
    }
    
    std::cout << maxEff;
}

/*
회고.
계속 처음 생각했던것과 뒤집어야 하는 방향으로 문제가 나온다.
저번 문제는 조건에 맞을때마다 확인했는데, 조건에 맞지 않을때 확인했어야 했고.
이번 문제도, 어떤 액션(빠지는 애 제외)을 따로 처리해줘야 했다.

비트를 써서 접근한건 좋았다. 칭찬해. 거의 접근을 다 했지만, 비트로 처음 접근했다고 배열을 안쓰는 것은 아니었다.
비트로 접근을 했다 하더라도 배열과 잘 섞어 써야겠다.
*/

주석이 되게 많은데, 처음 작성한 코드는 모든 연산을 비트마스크를 사용해 하려고 해서 너무 시간이 오래 걸렸다. 엄청 삽질하다가 좀 찾아보니 그냥 cnt를 만들어서 세주는것이 좋아보여 수정했다.

어떤 특정한 접근 방식을 정하고 나서, 그것만을 가지고 파려고 강박에 안 빠져도 될것 같다. 뭔가 항상 계속 열린 생각을 가지고 있어야겠다.

비트로 처음 접근한 것은 참 좋은 생각이었다. 칭찬해...

 

오늘도 평온한 하루가 되길. 슨민.