BOJ 4285 - Prerequisites?

문제

BOJ 4285 - Prerequisites?

학생이 이미 수강한 과목 목록과, 각 수강 신청 과목의 선수 과목 요건이 주어진다. 모든 수강 신청 과목의 선수 과목 요건을 충족하는지 판단한다. 각 과목은 최소 필요 선수 과목 이수 개수 b와 후보 선수 과목 목록으로 구성된다.

입력

• 각 테스트 케이스 첫 줄: N(이미 수강한 과목 수), M(신청할 과목 수)
• 다음 N개 줄: 이미 수강한 과목 번호
• 다음 M개 과목 정보: 각각 a b (후보 선수 과목 수, 최소 이수해야 할 개수) 후 a개의 과목 번호
• EOF까지 반복

출력

각 테스트 케이스마다 모든 과목의 선수 요건을 충족하면 yes, 하나라도 미달이면 no를 출력한다.

예제

풀이

이미 수강한 과목 번호를 불리언 배열에 표시해 두고, 각 신청 과목의 선수 과목 후보를 순회하며 이수 여부를 집계하는 문제다.

1. N, M을 읽어 테스트 케이스를 처리한다. EOF에서 종료한다.
2. N개의 기수강 과목 번호를 읽어 arr[] 불리언 배열에 true로 표시한다.
3. M개의 과목 정보를 읽는다. 각 과목에서 a개의 후보 과목과 최소 이수 개수 b를 읽는다.
4. a개의 후보 과목을 순회하며 arr[c]가 true이면 b를 1 감소시킨다.
5. 순회 후 b > 0이면 선수 과목 요건 미달로 답을 "no"로 설정한다.
6. M개 과목 처리 후 최종 답(yes/no)을 출력한다.

핵심 아이디어: 선수 과목 이수 여부를 O(1) 조회하기 위해 과목 번호를 인덱스로 쓰는 불리언 배열을 사용한다. 최소 이수 개수 b를 카운터로 활용해 이수 과목을 만날 때마다 감소시키면, 최종적으로 b > 0일 때 요건 미달임을 판단할 수 있다.

코드

#include <iostream>
 
using namespace std;
 
int main() {
  int n, m, num, a, b, c;
  while (cin >> n >> m) {
    bool arr[10000] = { 0 };
    while (n --) {
      cin >> num;
      arr[num] = 1;
    }
    string answer("yes\n");
    while (m --) {
      cin >> a >> b;
      while (a --) {
        cin >> c;
        if (arr[c] == 1) b --;
      }
      if (0 < b) answer = "no\n";
    }
    cout << answer;
  }
}

복잡도

• 시간: O(N + M * A) — 기수강 과목 등록 O(N) + 각 신청 과목의 선수 과목 순회 O(M * A)
• 공간: O(10000) — 과목 번호 최대 범위에 해당하는 불리언 배열