[백준 27375] 금공강 사수

조합론 + 비트마스크 문제이다

사실 DFS 문제이긴 한데 비트마스크 쓰는 부분이 훨씬 눈여겨볼만 한거 같아 비트마스크 쪽에 놓는다.

 

초반에는 5x10짜리 2차원 배열을 통해 나타내려고 했는데 비트마스크가 훨씬 깔끔할거 같아서 비트마스크로 품

 

일단 총 50시간을 표현하려면 32bit로는 부족하므로 64bit인 long long을 써줌

 

그리고 각 시간표를 비트로 나타내야하는데 이건 이렇게 하면 됨

각 요일마다 10시간이므로 특정 요일을 표현하려면 해당 요일 (정수값-1)*10 만큼 옮겨주고

해당 요일에서 끝나는 시간대를 통해 얼마나 더 shift 해줘야하는지 알아내면 됨

 

금요일은 아예 저장하지 않아도 되니까 입력받을때 무시하면 됨

 

해당 강의를 들을 수 있는지 확인하고 백트래킹으로 풀면 된다

 

백트래킹인 부분이 

if(sum > M)

이 부분이다.

M보다 커져서 더 이상 진행하지 않아도 되면 해당 탐색을 바로 종료하는 것이다.

 

---

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> arr;

int N, K;

// 5일 나타내려면 하루에 10시간이니까 50비트 필요
// int는 32비트니까 안됨 64비트짜리 써야함

int ans;

void DFS(int sum, int start,long long visited) {

	if (sum == K) { 
		ans++; 
		return; 
	}
	if (sum > K) return;

	// 조합이니까 전꺼 생각X
	for (int i = start+1; i<arr.size(); i++) {
		int day = arr[i][0];
		int front = arr[i][1];
		int end = arr[i][2];

		int cnt = end - front + 1; // 강의시간
		long long newbit = (1 << (cnt)) - 1;
		newbit = newbit << ((10 - end) + (day - 1) * 10);

		// 해당 시간이 공강이면
		if (!(visited & newbit)) {
			DFS(sum+cnt,i, visited | newbit);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N >> K;
	long long visited = 0;
	ans = 0;

	int day, front, end;
	for (int i = 0; i < N; i++) {
		cin >> day >> front>> end;
		if (day == 5) continue;
		vector<int> temp = { day,front,end };
		arr.push_back(temp);
	}
	DFS(0, -1, 0);
	cout << ans;
	return 0;
}