16.4 졸업 학기

1학년 때 엄청나게 논 태우를 도와주는 문제입니다. 

자세한 내용은 책을 참고해주시면 됩니다.

 

문제 : N개의 과목 중 K개 이상을 수강해야 졸업이 가능하다. 그리고 한 학기마다 열리는 강의의 수는 제한되어있고, 해당 과목을 수강하기 위해서는 선수과목을 들어야한다.

 

입력

테스트 케이스 C, 전공과목 수 N, 들어야하는 과목 수 K, 학기의 수 M, 한 학기 최대 수강 과목 수 L이 주어진다.

그리고 N개의 줄에 0번 과목부터 선수과목의 목록이 주어진다. 선수과목의 개수와 선수과목 목록을 입력받는다.

예를 들어, 2번 과목의 줄에 3 0 1 3 인 경우 선수과목 3개, 선수과목 목록 : 0,1,3 번 과목 인 것이다.

그 다음으로 해당 학기에 개설되는 과목의 수와 과목 목록을 입력받는다.

예를 들어, 2번 학기에 3 0 1 3인 경우 강의 3개가 열리고, 0,1,3번 과목이 열리는 것이다.

 

출력

태우가 다녀야 하는 최소 학기 수를 구하고, M이내에 졸업을 못하면 IMPOSSIBLE을 출력한다.

 

코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>

using namespace std;

int C, N, K, M, L; 
// C: test case, N: 전체 과목 수, K: 들어야할 과목 수
// M: 남은 학기 수, L: 한 학기 최대 수강 과목 수
int pre[12]; // i번째 과목의 선수과목의 집합
int classes[10]; // i번째 학기 개설 과목 집합
int dp[10][1 << 12]; 
// dp[i][j] : i번째 학기동안 j만큼 들었을 때 가능한 최소 학기 수

// 졸업 불가능
int INF = 987654321;

string line = "\n================================\n";

int bitcount(int n) // n의 이진수 값중 1의 개수 세기
{
	if (n == 0)
		return 0;
	return n % 2 + bitcount(n / 2);
}

// semester : 이번 학기 수, taken : 들은 과목 (집합으로 생각)
int graduate(int semester, int taken)
{ 
	// 기저 사례 : 들은 과목 수가 K 이상 : return
	if (bitcount(taken) >= K)
		return 0;
	// 기저 사례 : 학기 수 M 이상 : return
	if (semester == M)
		return INF;

	// result : semester 학기에 taken만큼 과목을 들었을 때 졸업까지 남은 최소 학기
	int& result = dp[semester][taken];
	if (result != -1)
		return result;
	result = INF;
	// canTake : semester 학기에 듣지 않은 과목 (~taken)
	int canTake = (classes[semester] & ~taken);

	// 선수 과목 듣지 않은 것 걸러냄
	for (int i = 0; i < N; i++) {
		if ((canTake & (1 << i)) && ((taken & pre[i]) != pre[i]))
			canTake &= ~(1 << i);
	}

	// 선수 과목 들은 것 (집합) 모두 탐색, 한 학기 최대 L개 수업
	for (int take = canTake; take > 0; take = ((take - 1) & canTake)) {
		if (bitcount(take) > L)
			continue;
		result = min(result, graduate(semester + 1, taken | take) + 1);
	}

	// 아무것도 듣지 않을 경우
	result = min(result, graduate(semester + 1, taken));
	return result;
}

int main()
{
	cout << "테스트 케이스 : ";
	cin >> C;
	cout << line;
	while (C--) {
		// 입력
		cout << "전체 과목 수, 들어야 할 과목 수, 남은 학기 수, 한 학기 최대 수강 과목 수 : ";
		cin >> N >> K >> M >> L;
		cout << line;

		// 초기화
		memset(dp, -1, sizeof(dp));
		memset(pre, 0, sizeof(pre));
		memset(classes, 0, sizeof(classes));

		// 선수과목 입력
		cout << "선수 과목 입력 : ";
		for (int i = 0; i < N; i++) {
			int idx;
			cin >> idx;
			for (int j = 0; j < idx; j++) {
				int num;
				cin >> num;
				pre[i] += pow(2, num);
			}
		}
		cout << line;

		// 개설 과목 입력
		cout << "개설 과목 입력 : ";
		for (int i = 0; i < M; i++) {
			int idx;
			cin >> idx;
			for (int j = 0; j < idx; j++) {
				int num;
				cin >> num;
				classes[i] += pow(2, num);
			}
		}
		cout << line;

		cout << "졸업까지 최소 학기 : ";
		int answer = graduate(0, 0);
		if (answer == INF)
			cout << "IMPOSSIBLE" << '\n';
		else
			cout << answer << '\n';
		cout << line;
	}
}