백준 1062번 가르침

www.acmicpc.net/problem/1062

 

 

 

백트래킹으로 풀 수 있는 문제이다.

가르칠 단어를 정하고 가르칠 수 있는지에 대한 여부를 확인할 때,

비트마스킹을 이용해 단어를  int형 변수에 저장하면 시간최적화가 가능하다.

 

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

#define MAX 50

int n, k;
bool visit[27];
int res;
string S[MAX+1];

void input() {
	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		cin >> S[i];
	}
}

int check_same() {
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		int len = S[i].length();

		bool suc = true;
		for (int j = 0; j < len; j++) {
			int idx = S[i][j] - 'a';
			if (!visit[idx]) {
				suc = false;
				break;
			}
		}
		if (suc) cnt++;
	}
	return cnt;
}

void dfs(int dep, int start) {
	if (dep == k) {
		res = max(res, check_same());
		return;
	}

	for (int i = start; i < 26; i++) {
		if (visit[i]) continue;
		visit[i] = true;
		dfs(dep+1, i+1);
		visit[i] = false;
	}
}

void setting() {
	string s;
	s.push_back('a'); s.push_back('n'); s.push_back('t'); s.push_back('i'); s.push_back('c');

	for (int i = 0; i < s.length(); i++) {
		visit[s[i]-'a'] = true;
	}
}

void solve() {
	input();

	if (k == 26) {
		res = n;
	}
	else if (k < 5) {
		res = 0;
	}
	else {
		setting();
		dfs(5, 0);
	}

	cout << res << '\n';
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	solve();
	return 0;
}

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int n, k, res;
int learn, word[50];

void input() {
	learn |= 1 << ('a' - 'a');
	learn |= 1 << ('n' - 'a');
	learn |= 1 << ('t' - 'a');
	learn |= 1 << ('i' - 'a');
	learn |= 1 << ('c' - 'a');

	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;

		int len = str.length();
		for (int j = 0; j < len; j++) {
			word[i] |= (1 << (str[j]-'a'));
		}
	}
}

void dfs(int dep, int start)
{
	if (dep == k) {
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			if ((word[i] & learn) == word[i]) {
				cnt++;
			}
		}
		res = max(res, cnt);
	}
	
	for (int i = start; i < 26; i++) {
		if ((learn & (1 << i)) == 0) {
			learn |= (1 << i);
			dfs(dep + 1, i + 1);
			learn &= ~(1 << i);
		}
	}
}

void solve() {
	input();

	if (k == 26) {
		res = n;
	}
	else if (k < 5) {
		res = 0;
	}
	else {
		dfs(5, 0);
	}

	cout << res << '\n';
}

int main(void)
{
	solve();
	return 0;
}

 

 

 

 

 

 

[참고]

onlytrying.tistory.com/m/154?category=837398