백준 1062 c++ "가르침" -PlusUltraCode-

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

 

[필자 사고]

문제에서 주어지는 특정 글자들은 이미 존재한다.

visited를 이용하여 미리 true형태로 해놓고

나머지 모든 문자열에 대해서 브루트포스 및 combination 즉 백트래킹을 이용해서 문제를 풀어보자

마지막 size가 원하는 K값과 같게 된다면 모든 문자열들을 확인하여 count값을 계산한다. 

위와 같이 문제를 풀었다. 

 

아래는 자세한 코드 해설이다.

[코드 해설]

Input 함수

• 사용자로부터 단어의 개수 N과 가르칠 수 있는 글자 수 K를 입력받는다.
• N개의 단어를 입력받아 arr 벡터에 저장한다.
• 동시에 myMap이라는 맵에도 해당 단어를 기록하지만, 이 맵은 이후 코드에서 사용되지 않기 때문에 불필요하다.

---

combination 함수

• 백트래킹을 사용해 26개의 알파벳 중에서 K개를 선택한다.
• 이미 선택된 글자는 visited 배열을 통해 확인하며, 알파벳을 선택할 때마다 재귀적으로 다음 알파벳을 선택한다.
• 선택한 글자가 K개가 되면, 현재 선택된 글자 조합으로 arr에 있는 단어들을 모두 검사한다.
  • 단어의 각 문자에 대해 visited 배열에 포함되지 않은 문자가 있다면 그 단어는 읽을 수 없다.
  • 모든 문자가 visited에 포함되어 있다면 읽을 수 있는 단어로 간주하고 카운트를 올린다.
• 지금까지의 최대 읽을 수 있는 단어 수를 resultCount에 기록한다.

---

Game_Start 함수

• K가 5보다 작으면 어떤 단어도 읽을 수 없으므로 0을 출력하고 종료한다.
• visited 배열을 26칸으로 초기화하고, 무조건 포함해야 하는 기본 글자 a, c, i, n, t를 true로 설정한다.
• 나머지 K - 5개의 글자를 선택하기 위해 combination 함수를 호출한다.
• combination 함수가 종료된 후, 최대로 읽을 수 있었던 단어 수 resultCount를 출력한다.

---

main 함수

• Input 함수로 입력을 받고, Game_Start 함수로 로직을 실행한다.

[소스 코드]

#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;

int N, K;
vector<string> arr;
map<string, int> myMap;
void Input() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;
		arr.push_back(str);
		myMap[str] = 1;
	}
}

vector<bool> visited;
int resultCount = 0;
void combination(int idx, int size) {
	if (size == K) {
		int count = 0;
		for (int i = 0; i < arr.size(); i++) {
			string str = arr[i];
			bool flag = false;
			for (int k = 0; k < str.size(); k++) {
				if (visited[str[k] - 'a'])continue;
				else {
					flag = true;
					break;
				}
			}
			if (flag == false) count++;
		}
		resultCount = max(resultCount, count);
		return;
	}

	for (int i = idx; i < 26; i++) {
		if (visited[i])continue;

		visited[i] = true;
		combination(i + 1, size + 1);
		visited[i] = false;
	}
}

void Game_Start() {
	if (K < 5) {
		cout << 0;
		return;
	}
	visited.resize(26, false);

	visited['a' - 'a'] = true;
	visited['c' - 'a'] = true;
	visited['i' - 'a'] = true;
	visited['n' - 'a'] = true;
	visited['t' - 'a'] = true;
	combination(0, 5);

	cout << resultCount;
}
int main(void) {
	Input();
	Game_Start();
}