🚀 [GRADUATION] 문제 😭😭😭😭😭
1학년은 노는 게 남는 거란 선배의 말을 철석같이 믿고, 전공 과목은 다 수강철회하고 교양 과목은 다 F 받는 방탕한 1학년을 보냈던 태우는 이제 와서 자신의 행동을 후회하고 있습니다. 졸업 전에 채워야 할 학점이 너무 많기 때문입니다. 졸업 필수 학점을 채우려면 전공 과목 N 개 중 K 개 이상을 수강해야 합니다. 그런데 각 과목은 해당 과목의 선수과목을 미리 수강했어야만 수강할 수 있으며, 각 학기마다 모든 과목이 개설되는 것이 아니기 때문에 문제가 복잡해졌습니다. 어떻게 해야 최소 학기에 졸업을 할 수 있을까요?
각 과목의 정보와 앞으로 M 학기 동안 개설될 과목의 목록이 주어질 때, 태우가 최소 몇 학기를 다녀야 졸업할 수 있는지 계산하는 프로그램을 작성하세요. 한 과목도 수강하지 않는 학기는 휴학한 것으로 하며, 다닌 학기 수에 포함되지 않습니다.
🔑 [풀이]
현재학기가 semester 이고 수강 하고있는 강의목록을 taken 이고 수강 학기 수를 반환하는 graduate(semester, taken) 함수를 생성합니다.
완전탐색으로 구현하되 시간을 줄이기 위해 메모이제이션 방법을 사용합니다. ()모든 경우의 수를 저장하는 cache를 사용)
재귀호출을 구현할 때 모든 조합을 만들기가 번거롭기 떄문에 비트마스크를 사용하여 코드를 쉽게 작성합니다.
자세한 내용은 코드 참조 바랍니다.
⌨️ 입력
입력의 첫 줄에는 테스트 케이스의 수 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을 출력합니다.
🖱 입력 예제
2
4 4 4 4
0
1 0
3 0 1 3
0
4 0 1 2 3
4 0 1 2 3
3 0 1 3
4 0 1 2 3
4 2 2 4
1 1
0
1 3
1 2
3 0 2 3
3 1 2 3
💻 출력 예제
3
IMPOSSIBLE
💎 전체 코드는 다음과 같습니다.
//
// GRADUATION.cpp
// AALGGO
//
// Created by inhyeok on 2021/11/26.
//
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("GRADUATION.txt");
int N; // 전공 과목수
int K; // 들어야할 과목수
int L; // 태우가 한학기에 들을 수 있는 최대 과목 수
int M; // 학기 수
const int MAXN = 12;
int pre_classes[MAXN];// 선수과목
int semester_classes[10]; // 해당 학기에 들을 수 있는 과목들
int cache[10][1<<MAXN];
const int INF = 987654321;
int bitcount(int taken){
return __builtin_popcount(taken);
}
// semester - 학기
// taken - 지금까지 수강한 강의
int graduate(int semester, int taken){
// 기저 사례 과목수를 다채웟으면 학기 리턴;
if(bitcount(taken) >= K) return 0;
// 과목수를 다 못채우면 INF 리턴
if(semester == M) return INF;
// 학기수 과목수
int &ret = cache[semester][taken];
if(ret!=-1 ) return ret;
ret = INF;
// 이번학기에 들을 수 있고 이미 듣지 않은것들
int canTake = ( semester_classes[semester] & ~taken);
for(int i = 0; i<N; i++){
if((canTake & (1<< i)) && (pre_classes[i]&taken)!=pre_classes[i] ){
canTake &= ~(1<<i);
}
}
// 수강할 수 있는 과목들의 경우의 수를 모두 순회한다.
for(int take = canTake ; take>0; take=((take-1)&canTake)){
if(bitcount(take)>L) continue;
ret= min(ret, graduate(semester+1, take|taken)+1);
}
// 휴학한 것으로 취급
// 학기 수에 포함하지않는다.
ret = min(ret, graduate(semester +1, taken));
return ret;
}
int main(){
int test_case;
fin >> test_case;
for(int test=0; test<test_case; test++){
fin >> N >> K >> M >> L;
memset(pre_classes, 0, sizeof(pre_classes));
memset(semester_classes, 0, sizeof(semester_classes));
memset(cache, -1 , sizeof(cache));
for(int i=0; i<N; i++){
int R; fin >> R;
for(int j=0; j<R; j++){
int ri; fin >> ri;
pre_classes[i] |= (1 << ri);
}
}
for(int i=0; i<M; i++){
int C; fin >> C;
for(int j=0; j<C; j++){
int ci; fin >> ci;
semester_classes[i] |= (1<< ci);
}
}
int result = graduate(0,0);
if(result == INF){
cout << "IMPOSSIBLE" << endl;
}
else{
cout<< result << endl;
}
}
}
Comments