[백준/C++] 1062. 가르침

문제

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

1062번: 가르침

남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

 

풀이

모든 단어에 공통되는 anta, tica부분을 자르고, 해당 알파벳 5개는 항상 알고있다고 설정한 뒤, 

DFS를 이용해서 k개의 알파벳을 뽑는다 (조합)

k개를 다 뽑았을 때에는, 해당 알파벳들을 알고있을 때 읽을 수 있는 단어의 수를 계산해서 

최종적으로 읽을 수 있는 단어의 수의 최댓값을 구하게 된다. 

 

비트맵을 쓰면 좋을 것 같은 문제이긴 한데, 알파벳 bool 배열을 이용해서도 풀 수 있었다. 비트맵을 이용하면 메모리가 줄어들겠지..?

코드

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

using namespace std;

int N, K, max_count;
bool alphabet[26];
vector<string> words;

int canReadNum() {
	bool isCanRead;
	int count = 0;
	for (int i = 0; i < words.size(); i++){
		isCanRead = true;
		string str = words[i];
		for (int j = 0; j < str.length(); j++){
			if (alphabet[str[j] - 'a'] == false){
				isCanRead = false;
				break;
			}
		}

		if (isCanRead == true){
			count++;
		}
	}
	return count;
}

void DFS_combi(int index, int count){
	if (count == K){ // k개 다뽑으면 해당 조합으로 읽을 수 있는 단어 개수 구하기
        int temp_count = canReadNum();
		max_count = max(max_count, temp_count);
		return;
	}

	for (int i = index; i < 26; i++){
		if (alphabet[i] == true) continue;
		alphabet[i] = true;
		DFS_combi(i, count + 1);
		alphabet[i] = false;
	}
}

int main(void){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> K;
	if (K < 5) {
		cout << 0 << endl;
		return 0;
	}
	K -= 5; // a,n,t,i,c 5개는 기본적으로 알고있음
	for (int n = 0;n < N;n++) {
		string input;
		cin >> input;
		input = input.substr(4, input.size() - 8); //모든 단어에 공통되는 부분 제거
		words.push_back(input);
	}
    // a,n,t,i,c 5개는 기본적으로 알고있음
	alphabet['a' - 'a'] = true;
	alphabet['n' - 'a'] = true;
	alphabet['t' - 'a'] = true;
	alphabet['i' - 'a'] = true;
	alphabet['c' - 'a'] = true;

	DFS_combi(0, 0);
	cout << max_count << endl;
	return 0;
}

결과