[Algospot] 졸업 학기 (문제 ID : GRADUATION)

문제

1학년은 노는 게 남는 거란 선배의 말을 철석같이 믿고, 전공 과목은 다 수강철회하고 교양 과목은 다 F 받는 방탕한 1학년을 보냈던 태우는 이제 와서 자신의 행동을 후회하고 있습니다. 졸업 전에 채워야 할 학점이 너무 많기 때문입니다. 졸업 필수 학점을 채우려면 전공 과목 N 개 중 K 개 이상을 수강해야 합니다. 그런데 각 과목은 해당 과목의 선수과목을 미리 수강했어야만 수강할 수 있으며, 각 학기마다 모든 과목이 개설되는 것이 아니기 때문에 문제가 복잡해졌습니다. 어떻게 해야 최소 학기에 졸업을 할 수 있을까요?

각 과목의 정보와 앞으로 M 학기 동안 개설될 과목의 목록이 주어질 때, 태우가 최소 몇 학기를 다녀야 졸업할 수 있는지 계산하는 프로그램을 작성하세요. 한 과목도 수강하지 않는 학기는 휴학한 것으로 하며, 다닌 학기 수에 포함되지 않습니다.

 

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 전공 과목의 수 N (1 <= N <= 12), 들어야 할 과목의 수 K (0 <= K <= N), 학기의 수 M (1 <= M <= 10) 과 태우가 한 학기에 최대로 들을 수 있는 과목의 수 L (1 <= L <= 10)이 주어집니다. 각 과목에는 0부터 N-1 까지의 번호가 매겨져 있습니다.

그 후 N 줄에 0번 과목부터 순서대로 각 과목의 정보가 주어집니다. 이 줄에는 해당 과목의 선수 과목의 수 Ri (0 <= Ri <= N-1) 가 처음 주어지고, 그 후 Ri 개의 정수로 선수 과목의 번호가 주어집니다.

그 후 M 줄에는 이번 학기부터 순서대로 각 학기의 정보가 주어집니다. 각 줄에는 해당 학기에 개설되는 과목의 숫자 Ci (1 <= Ci <= 10) 가 주어지고, 그 후 Ci 개의 정수로 개설되는 과목의 번호들이 주어집니다.

 

출력

각 테스트 케이스마다 한 줄에 태우가 다녀야 할 최소 학기 수를 출력합니다. M 학기 내에 졸업할 수 없는 경우 IMPOSSIBLE을 출력합니다.

---

입력부터 매우 많고, 비트 마스크를 써야 한다는 사실에 헷갈려한 문제이다.

여러 조건에 맞춰서 졸업할 수 있는 최소 학기를 구하는 문제이다.

함수 graduate(semester, taken) = 현재 semester 학기이고, taken의 수업을 들었을 때, 남아있는 최소 학기 수라고 하자.

dp를 활용할 것이기 때문에 이 정보를 저장하는 dp배열을 만든다.

기저 사례를 모두 처리한 후, 앞으로 들어야하는 과목 중 선수 과목을 듣지 않은 과목은 모두 제거한다. 그 남은 과목의 모든 부분집합중에 L과목을 넘지 않는 과목만 다음 학기로 넘기면서 완전탐색을 하면 풀 수 있다.

중간중간에 있는 비트마스크 기법들을 주의깊게 보자.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/GRADUATION.cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 987654321;
int C, N, K, M, L;
int prerequisite[12]; // i번째 과목의 선수과목
int classes[10]; // i번째 학기에 개설되는 과목의 집합
int dp[10][1 << 12];

int bitCount(int n)
{
	int cnt = 0;
	for (int i = 0; i < 12; i++)
		if (n & (1 << i)) cnt++;
	return cnt;
}

//현재 semester학기에서, 들은 과목의 집합 taken일때
//앞으로 다녀야 하는 최소 학기의 수
int graduate(int semester, int taken)
{
	//K개 이상의 과목을 이미 들은 경우
	if (bitCount(taken) >= K) return 0;
	//M학기가 지난 경우
	if (semester == M) return INF;

	int& res = dp[semester][taken];
	if (res != -1) return res;
	res = INF;

	//이번학기에 들을 수 있는 과목과 아직 안들은 과목
	int canTake = (classes[semester] & ~taken);

	//아직 선수과목을 다 듣지 않은 과목은 제외
	for (int i = 0; i < N; i++) {
		if ((canTake & (1 << i)) && (taken & prerequisite[i]) != prerequisite[i])
			canTake &= ~(1 << i);
	}

	//모든 부분집합 중에서 L개 이하의 과목을 듣는경우 다음 학기로 넘어간다.
	for (int take = canTake; take > 0; take = ((take - 1) & canTake)) {
		if (bitCount(take) > L) continue;
		res = min(res, graduate(semester + 1, taken | take) + 1);
	}

	//이번학기를 건너뛰는 경우
	res = min(res, graduate(semester + 1, taken));
	return res;
}
int main()
{
	cin >> C;
	while (C--) {
		cin >> N >> K >> M >> L;
		memset(classes, 0, sizeof(classes));
		memset(prerequisite, 0, sizeof(prerequisite));
		memset(dp, -1, sizeof(dp));

		for (int R, i = 0; i < N; i++) {
			cin >> R;
			for (int num, j = 0; j < R; j++) {
				cin >> num;
				prerequisite[i] |= (1 << num);
			}
		}
		for (int C, i = 0; i < M; i++) {
			cin >> C;
			for (int num, j = 0; j < C; j++) {
				cin >> num;
				classes[i] |= (1 << num);
			}
		}
		int res = graduate(0, 0);
		if (res >= INF)
			cout << "IMPOSSIBLE\n";
		else
			cout << res << "\n";
	}
	return 0;
}