AlgoSpot) GRADUATION

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

졸업하기위해 전공과목을 수강해야하는데 전공과목을 듣기위해서는 선행과목이 필요할수있다. 이런 제한조건을 가지고 최소학기에 졸업할수있는 학기를 출력하거나 불가능할경우 불가능을 출력하는 문제입니다.

이 문제는 비트마스크와 DP를 이용해서 문제를 풀었습니다.

비트연산을 이용해서 메모리 사용량을 줄이고 dp를 이용해서 탐색 시간을 줄였습니다.

처음에 입력부분에서 or 비트연산을 이용하지않고 (int)pow(2,n)연산을 이용해서 각과목에대한 선행과목 정보등을 더해가면서 표시했더니 테스트케이스는 정확히 나왔지만 사이트에서 답안 제출을 할때 오답이 나왔습니다. 

그리고 cache배열은 이진연산을 이용한 정보를 담을수있게 설계하였습니다.

함수 시작시 해당 학기에 열리는 과목에서 선수강되지않은 과목과 수강한 과목을 제외한 과목을 CanTake변수에 담습니다.

그후 수강가능한 과목들을 수강하면서 최적의 값을 구합니다.

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

int N, K, M, L; // 전공과목수, 들어야할 과목수, 학기의 수, 한학기 최대들을수있는 과목수

const int MAXN = 12;
const int IMPOS = 987654321;

int pre_sub[MAXN]; // 선수과목의 수
int classes[10]; // i 번학기에 개설되는 과목의 집합
int cache[10][1 << MAXN];

int bitCount(int n) {
	int bitcount = 0;
	int checkbit;
	for (int i = 0; i < 12; ++i) {
		checkbit = (1 << i);

		if ((checkbit & n) == 0) continue;
		else ++bitcount;
	}

	return bitcount;
	/*if (n == 0) return 0;
	return n % 2 + bitCount(n / 2);*/
}

int Graduate(int semester, int taken) {
	if (bitCount(taken) >= K) return 0;

	if (semester == M) return IMPOS;

	int& ret = cache[semester][taken];

	if (ret != -1) return ret;
	ret = IMPOS;

	int CanTake = (classes[semester] & ~taken); // 수강한 과목을 제외

	for (int i = 0; i < N; ++i) { // 선수강을 하지않은 과목을 제외
		if ((CanTake & (1 << i)) && (taken & pre_sub[i]) != pre_sub[i]) CanTake &= ~(1 << i);
	}

	for (int take = CanTake; take > 0; take = ((take - 1) & CanTake)) { // 수강할수있는과목의 경우의수를 전부 실행
		if (bitCount(take) > L) continue; // 한학기당 최대들을수있는 과목수를 초과하면 continue
		ret = min(ret, Graduate(semester + 1, taken | take) + 1); // 최소 학기수를 비교
	}

	ret = min(ret, Graduate(semester + 1, taken)); // 아무것도 안듣고 지나갈경우

	return ret;
}

void init() {
	memset(pre_sub, 0, sizeof(pre_sub));
	memset(classes, 0, sizeof(classes));
	memset(cache, -1, sizeof(cache));
}

int main() {
	std::ios::sync_with_stdio(false);
	freopen("test.txt", "r", stdin);
	int C, num, num2;
	cin >> C;
	cout << (int)pow(2.0, 11) << endl;
	while (C--) {
		cin >> N >> K >> M >> L;
		
		init();
		for (int i = 0; i < N; ++i) { // 전공과목 정보 입력
			cin >> num;

			for (int j = 0; j < num; ++j) {
				cin >> num2;
				//pre_sub[i] += (int)pow(2.0, num2);
				pre_sub[i] |= (1 << num2);
			}
		}

		for (int i = 0; i < M; ++i) {
			cin >> num;
			for (int j = 0; j < num; ++j) {
				cin >> num2;
				//classes[i] += (int)pow(2.0, num2);
				classes[i] |= (1 << num2);
			}
		}

		int answ = Graduate(0, 0);
		if (answ >= IMPOS) {
			cout << "IMPOSSIBLE" << endl;
		}
		else {
			cout << answ << endl;
		}
	}

	return 0;
}