졸업 학기

풀이

이 문제를 푸는 알고리즘 자체는 전형적인 지수 시간 동적 계획법입니다.

동적 계획법 알고리즘의 설계

동적 계획법 알고리즘을 만들기 위해서는 우선 완전 탐색 알고리즘을 설계하고 이것을 메모이제이션으로 최적화해야 합니다. 그리고 완전 탐색으로 문제를 풀기 위해서는 문제를 여러 조각으로 나눈 다음 한 조각을 해결하고 나머지를 재귀 호출을 통해 해결해야 합니다. 이 문제를 푸는 한 가지 자연스러운 방법은 각 학기를 한 조각으로 쪼개는 것입니다. 이를 위해 다음과 같은 부분 문제를 정의합니다.

$graduate(semester, taken)$=현재 학기가 $semester$이고, 지금까지 들은 과목의 집합이 $taken$일때, 앞으로 다녀야 하는 최소 학기의 수는?

$graduate()$를 완전 탐색으로 구현하는 방법은 각 학기마다 들을 수 있는 모든 과목의 조합들을 하나하나 시도해 보는 것입니다. 이번 학기에 개설되면서 선수 과목을 모두 들은 과목들 중, $L$개 이하의 모든 조합을 시도하는 것이죠. 이런 조합을 만드는 가장 일반적인 방법은 재귀 호출이지만, 여기서는 이미 $graduate()$라는 재귀 함수를 사용하고 있습니다. 따라서 이런 일을 하는 $choose()$라는 함수를 만들면 $graduate()$에서 $choose()$를 호출하고, $choose()$에서 스스로를 호출하다가 $L$개의 과목을 선택하고 나면 다시 $graduate()$를 호출해야 하는 등 코드의 구조가 너무 복잡해집니다.
이렇게 재귀 호출을 이용해 모든 조합을 만들기가 번거로울 때 비트마스크를 유용하게 쓸 수 있습니다.

구현

import java.util.*;

public class Main {

    public static int INF = 987654321;
    public static int N, K, M, L;
    // prerequisite[i] = i번째 과목의 선수과목의 집합
    public static int[] prerequisite;
    // classes[i] = i번째 학기에 개설되는 과목의 집합
    public static int[] classes;
    public static int[][] cache;

    public static int result;

    public static void input(Scanner scanner) {
        N = scanner.nextInt();
        K = scanner.nextInt();
        M = scanner.nextInt();
        L = scanner.nextInt();

        prerequisite = new int[N];
        for (int i = 0; i < N; i++) {
            int preCount = scanner.nextInt();
            for (int j = 0; j < preCount; j++) {
                prerequisite[i] |= (1 << scanner.nextInt());
            }
        }

        classes = new int[M];
        for (int i = 0; i < M; i++) {
            int classCount = scanner.nextInt();
            for (int j = 0; j < classCount; j++) {
                classes[i] |= (1 << scanner.nextInt());
            }
        }

        cache = new int[M][1 << N];
    }

    public static void solve() {
        result = graduate(0, 0);
    }

    // 이번 학기가 semester이고, 지금까지 들은 과목의 집합이 taken일 때
    // k개 이상의 과목을 모두 들으려면 몇 학기나 더 있어야 하는가?
    // 불가능한 경우 Integer.MAX_VALUE를 반환한다.
    public static int graduate(int semester, int taken) {
        // 기저 사례: k개 이상의 과목을 이미 들은 경우
        if (Integer.bitCount(taken) >= K) return 0;
        // 기저 사례: m 학기가 전부 지난 경우
        if (semester == M) return INF;
        // 메모이제이션
        if (cache[semester][taken] != 0) return cache[semester][taken];
        int result = INF;
        // 이번 학기에 들을 수 있는 과목 중 아직 듣지 않은 과목들을 찾는다.
        int canTake = (classes[semester] & ~taken);
        // 선수 과목을 다 듣지 않은 과목들을 걸러낸다.
        for (int i = 0; i < N; i++)
            if ((canTake & (1 << i)) > 0 && (taken & prerequisite[i]) != prerequisite[i])
                canTake &= ~(1 << i);
        // 이 집합의 모든 부분집합을 순회한다.
        for (int take = canTake; take > 0; take = ((take - 1) & canTake)) {
            // 한 학기에 L 과목까지만 들을 수 있다.
            if (Integer.bitCount(take) > L) continue;
            result = Math.min(result, graduate(semester + 1, taken | take) + 1);
        }
        // 이번 학기에 아무 것도 듣지 않을 경우
        result = Math.min(result, graduate(semester + 1, taken));
        return result;
    }

    public static void output() {
        if (result < INF)
            System.out.println(result);
        else
            System.out.println("IMPOSSIBLE");
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCase = scanner.nextInt();
        for (int i = 0; i < testCase; i++) {
            input(scanner);
            solve();
            output();
        }
    }
}

시간 복잡도 분석

이 코드의 시간 복잡도를 분석하기는 좀 까다롭습니다. $graduate()$ 내부의 반복문이 몇 번이나 수행되는가가 두 인자에 모두 영향을 받기 때문입니다. 그 상한만을 예측해 보기로 하겠습니다. $canTake$의 모든 부분 집합을 순회하려면 최대 $2^{C_i}$의 시간이 걸립니다. 전체 $M\cdot2^{N+C}$개의 부분 문제가 있으므로 프로그램의 전체 시간 복잡도는 $O(M\cdot2^{N+C})$이 됩니다. 입력의 최대치를 대입해 보면 이 값은 대략 4천만으로, 충분히 시간 내에 계산할 수 있음을 알 수 있습니다.