백준 1062번 : 가르침 (C++)

문제 : https://www.acmicpc.net/problem/1062

1062번: 가르침

 

K개의 알파벳만을 이용해서 최대한 많은 단어들을 가르쳐야하는 문제!

dp로 풀어야하나 했는데 n의 범위가 50이하인것을 보고 dfs 백트래킹으로 충분히 풀수있다 판단하였고 백트래킹 + 비트마스킹으로 해결하였다.

 

 

 

알파벳 a~z 는 0~25로 1대1 대응시키고 비트마스킹으로 만약 x를 가르친다면 state |= (x - 'a') 방법으로 비트마스킹 state 관리를 시켜주었다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include<cstring>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <unordered_map>
#include <deque>
#include <string>

typedef long long ll;

using namespace std;
int n, k;
string words[50];
ll states[51];
int ans =0;
ll df;


void dfs(int idx, int depth, ll state){
	
	
	if(depth == k){
		int num = 0;
		for(int i=0; i<n; i++){
			
			if( (states[i] & state) == states[i]){
				num++;
			}
		}
		ans = max(ans, num);

		return;
	}


	for(int i=idx; i<26; i++){
		if( (state&(1<<i)) ==0 ){
			dfs(i+1, depth+1, state|(1<<i));
		}
	}
	
}



int main()
{	

	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	df |=  (1<<('a'-'a'));
	df |=  (1<<('n'-'a'));
	df |=  (1<<('t'-'a'));
	df |=  (1<<('i'-'a'));
	df |=  (1<<('c'-'a'));

	cin >> n >> k;
	


	for(int i=0; i<n; i++)
		cin >> words[i];
	
	if(k<5){
		cout << 0;
		return 0;
	}
	if(k==26){
		cout << n;
		return 0;
	}

	for(int i=0; i<n; i++){

		ll state = df;
		for(int j=4; j<words[i].size()-4; j++){
			state  = state | (1<<(words[i][j]-'a'));
		}
		states[i] = state;
	}



	dfs(0, 5, df);



	cout << ans;


	return 0;
}