알고리즘 문제풀이
[알고스팟] 졸업학기 문제풀이
도리컴
2023. 2. 7. 00:44
반응형
코드를 더 깔끔하게 정리할 수 있지만, 일단 처음 풀었을 때는 이렇게 해결했음(풀이개념은 동일)
ㅇ
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
/*
<문제요약>
졸업 필수학점 채우려면 N개 과목 중 K개 이상 수강해야 함
각 과목은 선수과목이 존재
매 학기마다 개설되는 과목이 다름
한 학기당 최대 수강가능한 과목 수가 L개임
다녀야할 최소 학기 구하기(M학기 넘어가면 IMPOSSIBLE)
<입력>
C(테스트케이스 - <=50)
N(전공과목 수 - 0~12) K(들어야 할 과목 수 - 0~N) M(학기 수 - 1~10) L(태우가 한 학기에 최대 수강가능한 과목 수 - 1~10)
이후 N줄 - 각 과목의 정보
Ri(해당과목의 선수과목 수 - 0~N-1) a b c(선수과목의 번호 - R1 개 주어짐)
이후 M줄 - 각 학기 정보
Ci(해당 학기에 개설되는 과목 수 - 1~10) a b c(개설되는 과목 번호 - Ci 개 주어짐)
<출력>
각 테스트케이스 별 한 줄에 태우가 다녀야 할 최소학기 수 출력
M학기 내 졸업할 수 없는 경우, IMPOSSIBLE 출력
<풀이>
메모이제이션을 이용하는 것이 포인트 + 비트연산 할 줄 알아야함
graduate(a, b) -> a는 현재학기, b는 수강과목목록일 때 / 이 경우 다녀야하는 최소학기 수를 반환 -> cache에 해당 값 저장 후 재귀함수 때 이용
각 테스트케이스마다 초기화해야 하는 변수들 제대로 초기화 안해서 계속 오답떴었음..(괜히 엄한 곳에서 오랫동안 수정함)
cstring 헤더 써서 memset함수로 풀이 한 것들이 대부분임
*/
vector<int> prelearn; //[i]번 과목당 선수과목 표시
vector<int> semester; //각 학기별 개설과목 표시
int C;
int N, K, M, L;
int cache[10][1 << 12]; //cache[a][b] : a는 학기 수, b는 수강한 과목들 -> 이 때의 최소학기
int bitCount(int n) { //해당 수의 이진수 형태에서 1의 개수를 반환
if (n == 0)return 0;
return n % 2 + bitCount(n / 2);
}
//현재 학기, 수강과목들 -> 이 때의 최소학기 수 반환
int graduate(int cnt, int learned) { //휴학을 한 경우와 하지 않은 경우 중 최소인 경우의 학기를 반환
if (bitCount(learned) >= K) return 0;
if (cnt == M) return 987654321;
int& ret = cache[cnt][learned];
if (ret != -1) return ret;
ret = 987654321;
int tmp = ~learned; //~learned 계산
int canlearn = semester[cnt] & tmp; //이번학기 수강가능한 과목들 -> 이번학기 수강가능 && 수강안한과목
for (int i = 0; i < N; i++) { //각 과목마다
if ((canlearn & (1 << i)) && ((prelearn[i] & learned) != prelearn[i])) //canlearn의 각 선수과목 수강여부 확인해서 거르기
canlearn &= ~(1 << i);
}
for (int i = canlearn; i > 0; i = ((i - 1) & canlearn)) { //canlearn에서 선택해서 수강하는 경우 모두 탐색
if (bitCount(i) > L) continue;
ret = min(ret, graduate(cnt + 1, learned | i) + 1); //이번학기 카운트하고, 다음학기 계산했을 때 최소학기 수 더함
}
ret = min(ret, graduate(cnt + 1, learned)); //휴학했을 경우와 비교
return ret;
}
int main() {
cin >> C;
for (int i = 0; i < C; i++) { //testcase 반복
for (int ii = 0; ii < 10; ii++) //cache 모두 -1로 초기화, prelearn과 semester 초기화
for (int jj = 0; jj < (1 << 12); jj++) {
cache[ii][jj] = -1;
prelearn.erase(prelearn.begin(), prelearn.end());
semester.erase(semester.begin(), semester.end());
}
cin >> N >> K >> M >> L; //전공과목 수, 들어야하는 과목 수, 학기 수, 학기당 수강가능 과목 수
for (int i = 0; i < N; i++) { //각 과목정보 입력
prelearn.push_back(0);
int Ri; cin >> Ri; //해당 과목의 선수과목 수
for (int j = 0; j < Ri; j++) {
int a; cin >> a; //해당 과목의 선수과목 번호
prelearn[i] |= (1 << a);
}
}
for (int i = 0; i < M; i++) { //각 학기정보 입력
int Ci; cin >> Ci; //해당학기 개설과목 수
semester.push_back(0);
for (int j = 0; j < Ci; j++) {
int a; cin >> a; //해당학기 개설과목 번호
semester[i] |= (1 << a);
}
}
//각종 입력 및 prelearn, semester에 선수과목, 학기정보 저장 완료
int cnt = 0; //현재 학기
int learned = 0; //수강완료과목 목록
int ans = graduate(cnt, learned);
if (ans == 987654321) cout << "IMPOSSIBLE" << endl;
else cout << ans << endl;
}
}
|
cs |
반응형