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

 

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

 

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

---

 

 

해결전략

 

비트마스킹 Bitmasking
백트래킹

---

 

 

정답 코드

 

#include <algorithm>
#include <iostream>
#include <bitset>
#include <vector>
#include <set>
using namespace std;

int n, k;        // n: 단어의 수, k: 배울 수 있는 알파벳의 수
int answer;      // 최대 읽을 수 있는 단어의 수를 저장하는 변수

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

    cin >> n >> k;

    vector<string> words(n);  // 단어들을 저장할 벡터
    for (int i = 0; i < n; i++) {
        cin >> words[i];
    }

    // k가 5보다 작은 경우는 읽을 수 있는 단어가 없으므로 0을 출력
    if (k < 5) {
        cout << "0\n";
        return 0;
    }

    // 필수로 배워야 하는 알파벳 설정 (a, n, t, i, c)
    bitset<26> alphabet;
    alphabet['a'-'a'] = alphabet['n'-'a'] = alphabet['t'-'a'] = alphabet['i'-'a'] = alphabet['c'-'a'] = true;

    set<char> allCandidates;  // 추가로 배울 수 있는 알파벳 후보를 저장하는 집합
    for (int i = 0; i < n; i++) 
    {
        for (int j = 4; j < words[i].size() - 4; j++) // 각 단어의 문자 분석
        {
            if (false == alphabet[ words[i][j] - 'a' ]) { // 필수 알파벳이 아닌 경우에만 후보에 추가
                allCandidates.insert(words[i][j]);
            }
        }
    }

    vector<char> can(allCandidates.begin(), allCandidates.end());  // 후보 알파벳을 벡터로 변환
    int canSize = can.size();  // 후보 알파벳의 수

    // 조합을 이용한 가능한 모든 경우의 수를 확인하기 위한 벡터 초기화
    vector<bool> comb(canSize, false);
    fill(comb.begin() + canSize - min(canSize, k - 5), comb.end(), true); // k - 5를 고려하여 초기화

    do {
        bitset<26> learned = alphabet;  // 현재 조합에서 배운 알파벳을 저장하는 비트셋

        for (int i = 0; i < canSize; i++) 
        {
            // 현재 조합에서 선택된 알파벳을 learned 비트셋에 추가
            if (comb[i]) {
                learned[can[i] - 'a'] = true;
            }
        }

        int cnt = 0;  // 현재 조합으로 읽을 수 있는 단어의 수
        for (int i = 0; i < n; i++) 
        {
            bool canRead = true;  // 현재 단어를 읽을 수 있는지 여부

            for (int j = 0; j < words[i].size(); j++) 
            {
                // 현재 단어의 모든 문자가 learned 비트셋에 있는지 확인
                if (false == learned[ words[i][j] - 'a' ]) {
                    canRead = false;
                    break;
                }
            }

            // 단어를 읽을 수 있는 경우 카운트 증가
            if (canRead) {
                cnt++;
            }
        }

        answer = max(answer, cnt); // 최대 읽을 수 있는 단어의 수를 업데이트

    } while (next_permutation(comb.begin(), comb.end()));

    cout << answer << "\n";
    
    return 0;
}

 

---

 

 

정답코드2

 

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

int n, k;
int answer;
vector<int> words;

// DFS를 사용하여 알파벳의 조합을 찾는 함수
void DFS(int len, int alpha, int hash)
{
	if (len == k) // 알파벳 k개 선택 완료
	{		
		int result = 0;

		// 현재 hash값으로 읽을 수 있는 word 개수 카운팅
		for (int i = 0; i < n; i++)
		{
			if ((hash & words[i]) == words[i]) { // 현재 선택된 알파벳이 단어에 포함되어 있는지 확인
				result++;
			}
		}

		answer = max(answer, result);
		return;
	}

	// 26개 알파벳 중 아직 선택되지 않은 알파벳을 선택. 26개 알파벳 중 k - 5개 알파벳 선택.
	for (int i = alpha; i < 26; i++)
	{
		if (hash & (1 << i)) continue; // 이미 선택된 알파벳은 건너뛰기

		DFS(len + 1, i + 1, hash | (1 << i));	// 다음 알파벳 선택
	}
}

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

	cin >> n >> k;
	words.resize(n);

	string input;
	for (int i = 0; i < n; ++i) {
		cin >> input;
		
		for (int j = 0; j < input.size(); ++j) { // 입력 단어에 대한 hash값 계산 후 저장.
			words[i] |= (1 << (input[j] - 'a'));
		}
	}
	
	
	int hash = 0;
	string essentialAlphabet = "acint";
	for (int i = 0; i < essentialAlphabet.size(); i++)
	{
		hash |= (1 << (essentialAlphabet[i] - 'a')); // 필수 알파벳 'a', 'c', 'i', 'n', 't'를 hash에 추가.
	}


	if (k < 5) { // k가 5보다 작은 경우는 필수 알파벳만으로는 단어를 읽을 수 없으므로 0 출력
		cout << "0";
	}
	else if (k >= 26){ // k가 26인 경우는 모든 알파벳을 배울 수 있으므로 모든 단어를 읽을 수 있음
		cout << n;
	}
	else
	{
		DFS(5, 0, hash); // 5는 필수 알파벳을 이미 선택했으므로 DFS를 5에서 시작

		cout << answer;
	}

	return 0;
}

 

 

 

---