[알고스팟 / 비트마스크 DP] GRADUATION 졸업학기

https://algospot.com/judge/problem/read/GRADUATION#

 

algospot.com :: GRADUATION

 

문제 풀이 전

군대에서 처음 올리는 글입니다.

VS를 쓰다 구름IDE를 쓰고 디버깅을 안하면서 하다보니코드가 많이 복잡해진 감이 있네요. 양해 부탁드립니다.

꾸준히 글은 작성하지 못하지만 문제는 꾸준히 풀도록 노력하겠습니다.

D-546 ㅎㅎ

 

 

GADUATION 졸업학기

 

알고리즘 : 비트마스크 DP (with BFS)

비트마스크를 이용한 작은 양의 데이터 처리에 익숙해 질 수 있는 문제입니다.수강가능 학기, 선수강, 이미 들은 과목 등 거의 모든 정보를 비트마스크로 처리하고최소 수강 학기를 동적계획법을 이용해 시간을 줄이는 풀이를 사용합니다.

 

__builtin_popcount 

: 현재 수의 켜진 비트 수(1의 개수) 반환 함수, O(1)

 

CHECK POINT

한 과목도 수강하지 않는 학기는 휴학한 것으로 하며, 다닌 학기 수에 포함되지 않습니다.

최소 학기의 번호가 아니라 최소 다닌 학기의 수 입니다.

 

예상 예외

1
4 4 5 4
0
0
0
0
1 0
1 1
1 2
1 3
4 0 1 2 3

 

 

 

 

 

 

 

 

 

 

 

 

 

< CODE >

//https://algospot.com/judge/problem/read/GRADUATION

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

#define MAX 14

struct forQ
{
	int now; // 현재학기
	int cur; // 현재수강
	int possible; // 수강가능과목
	int rest; // 휴학한 학기 수
};

queue<forQ> q;
int pBit[MAX];
int scheBit[MAX];
int chk[MAX][1 << MAX];

void init() // testCase 마다 초기화
{
	for(int i = 0; i < MAX; i++)
	{
		pBit[i] = 0;
		scheBit[i] = 0;
		
		for(int j = 0; j < (1 << MAX); j++)
			chk[i][j] = -1;
	}
	
	while(!q.empty())
		q.pop();
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int test;
	
	cin >> test;
	
	while(test--)
	{
		init();
		
		int n,k,m,l;
		int possible = 0;
		
		cin >> n >> k >> m >> l;
		
		for(int i = 0; i < n; i++) // 선수강
		{
			int prev;
			
			cin >> prev;
		
			if(prev == 0)
				possible |= (1 << i);
			
			for(int j = 0; j < prev; j++)
			{
				int num;
				
				cin >> num;
				
				pBit[i] |= (1 << num);
			}
		}
		
		for(int i = 0; i < m; i++) // 학기
		{
			int scale;
			
			cin >> scale;
			
			for(int j = 0; j < scale; j++)
			{
				int num;
				
				cin >> num;
				
				scheBit[i+1] |= (1 << num);
			}
		}
		
		q.push({1,0,possible,0});
		int result = 987654321;
		
		while(!q.empty())
		{
			forQ cur = q.front(); q.pop();
						
			if(cur.rest < chk[cur.now - 1][cur.cur]) // 수강한 과목이 똑같은 데 휴학한 학기 수가 적을 경우
				continue;
			
			if(__builtin_popcount(cur.cur) >= k)
			{
				result = min(result,cur.now - cur.rest - 1);
				continue; // break 사용시 예외케이스 발생
			}
			
			if(cur.now == m+1)
				continue;
			/* i가 암시하는 것
			이번학기에 1 = 0001 0번과목만, 2 = 0010 1번과목만, 9 = 1001 0,3번 과목 동시 수강
			*/
			for(int i = 1; i <= scheBit[cur.now]; i++)
			{
				int tPos = cur.possible;
				
				// 이미 수강한 과목이 있거나 듣는 과목수가 최대 과목수를 초과하거나 수강불가능한 과목을 듣는 경우 ㄴㄴ
				if((cur.cur & i) == 0 && __builtin_popcount(i) <= l && (i & cur.possible) == i && (i & scheBit[cur.now]) == i)
				{
					int next = cur.cur | i;
					if(cur.rest > chk[cur.now][next])
					{
						chk[cur.now][next] = cur.rest;
						
						for(int ii = 0; ii < n; ii++)
							if((pBit[ii] & next) == pBit[ii])
								tPos |= (1 << ii);
						
						q.push({cur.now+1,next,tPos,cur.rest});						
					}
				}
			}
			
			q.push({cur.now+1,cur.cur,cur.possible,cur.rest + 1});	
		}
		
		if(result == 987654321)
			cout << "IMPOSSIBLE\n";
		else
			cout << result << '\n';
	}
}

시간 : 192ms

 

태그 : #종만북 졸업학기 #algospot graduation #알고스팟 졸업학기