백준 1497 - 기타콘서트

https://www.acmicpc.net/problem/1497

1497번: 기타콘서트

N과 M의 크기가 크지 않아 비트마스킹 기법으로 풀 수 있는 문제

 

문제 접근 방식은 이런 식이다.

기타 N개로 만들 수 있는 2^N개의 조합(공집합 제외)에 대해, 각 조합에 속한(& 연산 사용) 기타들을 모두 사용했을 때 연주할 수 있는 곡 수가 최대가 되는 조합을 찾으면 된다.

 

코드 보기

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

int main() {
	int N, M, i;
	cin >> N >> M;

	vector<string> v;
	string str;
	for (i = 0; i < N; i++) {
		cin >> str; cin >> str;
		v.push_back(str);
	}
	int max = 0, cnt = -1;

	int guitar, song;
	for (int i = 0; i < (1 << N); i++) {
		vector<int> vis(M);
		guitar = song = 0;

		//i : 사용 가능한 기타의 조합
		//j : 사용하는 기타
		for (int j = 0; j < N; j++) {
			if (i & (1 << j)) {
				guitar++;
				for (int k = 0; k < M; k++) {
					if (v[j][k] == 'Y' && vis[k] == 0) {
						vis[k] = 1;
						song++;
					}
				}
			}
		}

		if (song > max) {
			//곡의 개수가 더 많아지면 cnt 갱신
			max = song;
			cnt = guitar;
		}
		else if (song == max && cnt > guitar) {
			//곡의 개수가 동일할 때는 cnt를 최소값으로
			cnt = guitar;
		}
	}

	cout << cnt << endl;
}