[비트 마스크] GRADUATION 졸업 학기 문제

1. 비트 마스크 문제

 

부울 배열들을 비트 마스크 로 풀어내는 문제이다.

 

과목 => 선수과목

학기 => 과목

 

학기마다 선수과목이 포함되어 있는지 확인하고.

강의를 들을 수 있는 과목을 선택하여

조합 탐색하면 쉽게 답을 구할 수 있다.

 

tmpSelect = semester[j] & (~select);

=> 이번 학기에 들을 수 있는 수업중 이미 수강한것은 제외시킨다.

=> 최상위 비트또한 반전되어 없어진다.

=> 모든학생이 이번 학기에 들을 수 있는 강의들

 

if((tmpSelect&(1<<i))&& (select&R[i]) != R[i])

       tmpSelect &= ~(1<<i);

=> 이번 학기에 들을 수 있는 강의 중 내가 선수 과목을 전부 이수하지 못한것은 빼버린다.

=> 내가 이번 학기에 들을 수 있는 강의들

 

int tmpSelect = (1<<N );

if(((C[semester] & (1<<i)) != 0 )&& ((select & (1<<i) )!= (1<<i)) && ((select&R[i]) == R[i]))
    tmpSelect |= (1<<i);

=> 이번학기에 들을 수 있고, 아직 듣지 않고, 선수 과목을 이수 했을 경우

=> 내가 이번 학기에 들을 수 있는 강의들

2. 그리드

 

학기중에 최대 들을 수 있는 수업 수 보다 

내가 이번 학기에 들을 수 있는 강의들이 작으면 

전부 수업을 듣는 방법을 구현해보았는데도 오답이 나왔다.

 

 

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <utility>
 
using namespace std;
 
int testCase;
 
int N;//lecture // 12
int K;//required // N
int M;//semester // 10
int L;//1semester Max lecture //10
 
 int R[12];// lecture  -> prerequisite
 int C[10];// semester -> lecture
 
int bitCount( int x)
{
    if(x == 0) return 0;
    return x%2 + bitCount(x/2);
}
 
int cache[1<<13][11];
 
int thisSemester(int semester,  int select)
{
    if(bitCount(select) - 1 == K) return 0;
    if(semester == M) return 1234567;
    
    int &ret = cache[select][semester];
    if(ret != -1) return ret;
    
     int tmpSelect = (C[semester]&~select);
 
    for(int i = 0; i < N; i++)
    {
        if((tmpSelect&(1<<i))&& (select&R[i]) != R[i])
            tmpSelect &= ~(1<<i);
    }
    ret = 1234567;
 
    for(int subSet = tmpSelect; subSet>0; subSet = ((subSet-1)&tmpSelect))
    {
        int subSetSize = bitCount(subSet);
        if(subSetSize <= L)
            ret = min<int>(ret, thisSemester(semester + 1, select|subSet)+1);           
    }
    ret = min(ret, thisSemester(semester+1, select));
    return ret;
}
 
 
int main()
{
    int num = 0;
    int tmp = 0;
 
    cin>>testCase;
    for(int i = 0; i < testCase; i++)
    {
        memset(cache, -1, sizeof cache);
 
        cin>>N>>K>>M>>L;
        for(int j = 0; j < N; j++)
        {
            int state = 1<<N;
            cin>>num;
            for(int k = 0; k < num; k++)
            {
                cin>>tmp;
                state |= (1<<tmp);
            }
            R[j] = state;
        }
        for(int j = 0; j < M; j++)
        {
            int state = 1<<N;
            cin>>num;
            for(int k = 0; k < num; k++)
            {
                cin>>tmp;
                state |= (1<<tmp);
            }
            C[j] = state;
        }
 
        int ret = thisSemester(0,1<<N);
 
        if(ret > M) 
            cout<<"IMPOSSIBLE\n";
        else 
            cout<<ret<<"\n";
    }
}

GRADUATION