백준 1062 가르침 C언어, C++ - DFS완전탐색

 

단어를 정해진 수 K개만 가르쳐주고 N개의 단어를 읽게 하는 잔인한 문제다.

N <= 50 이고 K<=26 이며 단어의 길이는 8<= l <= 15 이다.

 

구성은 다음과 같다.

 

1. 단어는 항상 anta + ' ' + tica 의 형식을 가지기 때문에 a n t i c 은 항상 알고 있어야만 한다.

그러므로 K-=5 를 해주고 a n t i c 을 안다고 가정해야하고 , 이 때 K<0 이면 antic 조차도 모른다는 뜻이니

항상 0개이다.

 

2. K-5 개에 대해서 DFS를 이용하여 완전탐색을 실시하면서 각자 단어가 몇 개씩 맞는지를 센다.

 

완전탐색을 수행한다면,

시간복잡도는 N(50) * ( (21)C(K-5) ) * l(15) 이고 K-5가 10일 때 최대이므로

계산해보면 1억이 훌쩍 넘는다. (2억6천만 이상)

부분최적화로 1/3 수준으로 떨어뜨려야하..는데?

통과가 됐다.

 

아무래도 극단적인 케이스 ( N=50 , l=15(all) , K=15) 가 안나온게 아닐까..?

 

count()는 anta 뒤부터 알파벳 하나씩 배운건지 확인하고, 모두 아는 알파벳이면 ret를 +1 아니면 +0을 하여

N개를 모두 매칭 후에 아는 단어의 수를 return 한다.

 

sol()함수는 DFS 로 안배운 알파벳을 하나씩 배워나가면서 K-5개만큼 모두 배우고 나면 count()를 호출하여

아는 단어의 개수를 세준다.

 

main()에서는 필수적으로 알아야하는 알파벳인 antic를 미리 배우게 해놓고 K에 5를 빼준 후에 dfs를 수행한다.

 

전체코드

#include <stdio.h>
#include <string.h>
int N, K;
char Word[52][17];
int learned[26];
int max;

int count() {
	int ret = 0;
	for (int i = 0; i < N; i++) {
		//anta 까진 같음
		int j = 4;
		int know = 1;
		for (;;) {
			if (Word[i][j] == 0x0) break;
			if (!learned[Word[i][j] - 'a']) {
				know = 0; break;
			}
			j++;
		}
		if (know) ret++;
	}
	return ret;
}

int sol(int n,int idx) {
	if (n >= K) {
		int cnt = count();
		if (cnt > max) max = cnt;
		return 0;
	}
	for (int i = idx; i < 26; i++) {
		if (!learned[i]) {
			learned[i] = 1;
			sol(n +1, i );
			learned[i] = 0;
		}
	}


	return 0;
}

int main() {
	//입력
	scanf("%d %d", &N, &K);
	for (int i = 0; i < N; i++) {
		scanf("%s", Word[i]);
	}
	//필수적으로 알아야할 단어
	learned['a' - 'a'] = 1;
	learned['n' - 'a'] = 1;
	learned['t' - 'a'] = 1;
	learned['i' - 'a'] = 1;
	learned['c' - 'a'] = 1;
	K -= 5;
	if (K < 0) {
		printf("%d", 0);
		return 0;
	}
	sol(0,0);
	printf("%d", max);
	return 0;
}

 

---

C++ 코드

c++에서는 algorithm 과 string header를 사용했고, bool을 사용한 것외에 논리는 같다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

static int N, K, Answer = 0;
static bool Alpha[26] = {};

vector<string> noun;

int reading() {
	bool can;
	int MAX = 0;
	for (int i = 0; i < noun.size(); i++)
	{
		string NOUN = noun[i];
		can = true;
		for (int j = 0; j < NOUN.length(); j++)
		{
			if (Alpha[NOUN[j] - 'a'] == false)
			{
				can = false;
				break;
			}
		}
		if (can == true)
			MAX += 1;
	}
	return MAX;
}

void dfs(int index, int count) {
	if (count == K) {
		Answer = max(Answer, reading());
		return;
	}
	for (int i = index; i < 26; i++){
		if (Alpha[i])
			continue;
		Alpha[i] = true;
		dfs(i, count+1);
		Alpha[i] =false;
	}
}










int main()
{
	Alpha['a' - 'a'] = 1;
	Alpha['n' - 'a'] = 1;
	Alpha['t' - 'a'] = 1;
	Alpha['i' - 'a'] = 1;
	Alpha['c' - 'a'] = 1;
	cin >> N >> K;
	
	
	for (int i = 0; i < N; i++)
	{
		string input;
		cin >> input;
		noun.push_back(input);

	}
	if (K < 5) {
		cout << 0 << "\n";
		return 0;
	}
	K -= 5;
	dfs(0, 0);
	cout << Answer << "\n";

	return 0;

}