알고스팟: 졸업 학기 (ID: GRADUATION)

[문제 링크]

algospot.com :: GRADUATION

---

알고리즘 문제해결전략의 비트마스크 부분을 공부하면서 풀게된 첫 문제였다.

 

주어지는 입력의 범위가 20 미만으로 작기 때문에 최대 32비트 길이의 2진수를 표현할 수 있는 int형 정수의 비트연산을 통해 효율적으로 정답을 구할 수 있다.

---

#include <iostream>
#include <cstring>
using namespace std;

const int INF = 987654321;
int N, K, M, L;
int preceding[12], classes[10];
int memo[10][1 << 12];

int min(int a, int b) { return a < b ? a : b; }

int BitCount(int taken)
{
	int cnt = 0;

	for (int i = 0; i < N; i++)
		if (taken & (1 << i))
			cnt++;

	return cnt;
}

int Topdown(int semester, int taken)
{
	if (BitCount(taken) >= K) return 0;
	if (semester >= M) return INF;

	int& ret = memo[semester][taken];
	if (ret != 0) return ret;

	ret = INF;

	int canTake = (classes[semester] & ~taken);

	for (int i = 0; i < N; i++)
		if ((canTake & (1 << i)) && (preceding[i] & taken) != preceding[i])
			canTake &= ~(1 << i);

	for (int take = canTake; take > 0; take = ((take - 1) & canTake))
	{
		if(BitCount(take) > L) continue;
		
		ret = min(ret, 1 + Topdown(semester + 1, taken | take));	
	}

	ret = min(ret, Topdown(semester+1, taken));

	return ret;
}

int main(void)
{
	int test_case;
	cin >> test_case;

	while (test_case--)
	{
		memset(preceding, 0, sizeof(preceding));
		memset(classes, 0, sizeof(classes));
		memset(memo, 0, sizeof(memo));

		cin >> N >> K >> M >> L;

		
		for (int i = 0; i < N; i++)
		{
			int R;
			cin >> R;
			
			for (int j = 0; j < R; j++)
			{
				int num;
				cin >> num;
				preceding[i] |= (1 << num);
			}
		}

		for (int i = 0; i < M; i++)
		{
			int C;
			cin >> C;

			for (int j = 0; j < C; j++)
			{
				int num;
				cin >> num;
				
				classes[i] |= (1 << num);
			}
		}

		int result = Topdown(0, 0);

		if (result == INF)
			cout << "IMPOSSIBLE" << endl;
		else
			cout << result << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 134 day