백준 15361번 Izbori

문제 링크입니다: https://www.acmicpc.net/problem/15361

15361번: Izbori

비트마스킹을 이용한 백트래킹 문제였습니다.

현재 뽑히는 사람이 K가 아니라면 비트마스킹을 이용하여 한명한명 기권시켜보며 최소 몇명을 기권시켜야 K가 뽑히는지 파악해야합니다.

비트마스킹 개념만 안다면 코드를 해석하는데 어려움은 없을 것이라고 생각합니다.

 

	#include <iostream>
	#include <algorithm>
	#include <functional>
	using namespace std;
	const int INF = 987654321;
	int N, M, K;
	int candidate[100][15];
	int result;
	void func(int bit, int j, int cnt)
	{
	int ranks[16] = { 0, };
	int idx = -1;
	int cnt1 = 0;
	for (int i = 0; i < N; i++)
	{
	int j = 0;
	//기권하는 사람들은 세지 않는다
	while (bit & (1 << (candidate[i][j])))
	j++;
	ranks[candidate[i][j]]++;
	}
	//현재 뽑힐 사람 구함
	for(int i=1; i<=M; i++)
	if (ranks[i] > cnt1)
	{
	idx = i;
	cnt1 = ranks[i];
	}
	//뽑히는 사람이 K라면 더 이상 기권 X
	if (idx == K)
	{
	result = min(result, cnt);
	return;
	}
	//뽑히는 사람이 K가 아니기 때문에 다음 기권할 사람
	for (int i = j + 1; i <= M; i++)
	//비트마스킹을 통해 표현
	if(!(bit & (1 << i)))
	func((bit | (1 << i)), i, cnt + 1);
	}
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++)
	for (int j = 0; j < M; j++)
	cin >> candidate[i][j];
	int cnt = 0;
	int idx1 = -1;
	int ranks[16] = { 0, };
	for (int i = 0; i < N; i++)
	ranks[candidate[i][0]]++;
	//현재 뽑히는 사람 구함
	for(int i = 1; i <= M; i++)
	if (ranks[i] > cnt)
	{
	idx1 = i;
	cnt = ranks[i];
	}
	cout << idx1 << "\n";
	//뽑히는 사람이 K라면
	if (K == idx1)
	cout << 0 << "\n";
	//뽑히는 사람이 K가 아니라면
	else
	{
	result = INF;
	int bit = 1 << (M + 1);
	//비트마스킹을 통해 기권하는 사람 표현
	for(int i=1; i<=M; i++)
	func(bit | (1 << i), i, 1);
	cout << result << "\n";
	}
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~