BOJ 16457 단풍 이야기

 

16457번: 단풍잎 이야기

• 퀘스트를 나타내는 방법(자료구조)
  • 처음에는 배열을 생각했다. 하지만 선택된 스킬로 퀘스트를 수행할 수 있는지 비트 연산만으로 파악할 수 있도록 비트마스크로 퀘스트를 나타내기로 했다.
• 조합을 탐색하는 방법(알고리즘)
  • 브루트포스(재귀)
    • 브루트포스로 2n개의 스킬 중 n개 선택
    • m개의 퀘스트 중 수행할 수 있는 개수 계산(동일)
    • O(C(2n, n) * m)
  • 비트마스크(loop)
    • 비트마스크를 0부터 2n까지 loop을 돌려 n개의 bit이 set된 것 선택
    • m개의 퀘스트 중 수행할 수 있는 개수 계산(동일)
    • O(2^(2n) + C(2n, n) * m)
  • 실제 수행시간은 브루트포스의 재귀 overload를 고려해야 하기 때문에 어떤 것이 더 빠르다고 단정짓기 어렵다.
• 주의사항
  • 비트연산자의 우선순위는 비교 연산자보다 낮다.
  • 비교 대상에 비트연산자가 포함되어 있다면 꼭 괄호를 붙이자

// 1. 스킬번호 0부터 시작
/* 1. 연산자 우선순위 : bitwise 연산자는 항상 괄호 붙일것! */
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, k;
int quests[100];
int ans;
// 브루트포스로 스킬셋 비트마스크 생성
void bf(int i, int s, int bm) {
	if (s == n) {
		int quest_ctr = 0;						// 수행 가능한 퀘스트 카운터
		for (int q = 0; q < m; ++q) {
			if ((bm & quests[q]) == quests[q]) { // 선택된 스킬들로 q번째 퀘스트를 수행할 수 있으면
				++quest_ctr;						// 카운터를 증가
			}
		}
		ans = max(ans, quest_ctr);				// 카운터의 최댓값이 정답
		return;
	}
	for (; i < 2 * n; ++i) {
		bf(i + 1, s + 1, bm | 1 << i);
	}
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
    // 퀘스트 별로 요구되는 스킬을 비트마스크로 나타내기
	for (int q = 0; q < m; ++q) {
		int bitmask = 0;
		for (int _ = 0; _ < k; ++_) {
			int skill;
			cin >> skill;
			bitmask |= 1 << (skill - 1);	// 1.
		}
		quests[q] = bitmask;
	}
	bf(0, 0, 0);
	cout << ans;
	return 0;
}