[백준][완전탐색] 1062 가르침 c++ 구현

목차

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

문제

 

 

문제 구현 방향

조합을 이용해 모든 경우의 수를 구해서 풀었다. 

조합을 구하는 방법은 아래를 참고하자

 

참고

https://be-senior-developer.tistory.com/49

[알고리즘] 순열과 조합 c++ 구현

 

 

 

코드 구현

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<math.h>
#include<map>

using namespace std;

int N, K;

vector<string> str;
map <char, int> m;
vector<char> target;
vector<char> comb;
int maxA = 0;

//
int check() {
	int cnt = 0;
	for (auto s : str) {
		bool canRead = true;
		for (int i = 0; i < s.size(); i++) {
			if (!m[s[i]]) {
            //이렇게 중단을 안넣어주면 시간 초과가 나니 주의하자
				canRead = false;
				break;
			}
		}
		if (canRead)
			cnt++;
	}
	return cnt;
}

//조합을 통한 완전탐색
void combi(int here, int n) {
	
	if (n == K - 5) {
	
		for (auto p : comb)
			m[p] = 1;
		maxA = max(maxA , check());
		for (auto p : comb)
			m[p] = 0;
		return;
	}
	for (int i = here+1; i < target.size(); i++) {
		comb.push_back(target[i]);
		combi(i, n+1);
		comb.pop_back();
	}
}


int main() {
	string S;
	cin >> N >> K;
	m.insert({ 'a', 1 });
	m.insert({ 'n', 1 });
	m.insert({ 't', 1 });
	m.insert({ 'i', 1 });
	m.insert({ 'c', 1 });

	if (K < 5) {
		cout << 0;
		return 0 ;
	}
	for (int i = 0; i < N; i++) {
		cin >> S;
		str.push_back(S);
	}
	for (auto s : str) {
		for (int i = 0; i < s.size(); i++) {
			if (s[i] != 'a' && s[i] != 'n' && s[i] != 't' && s[i] != 'i' && s[i] != 'c') {
				auto it = find(target.begin(), target.end(), s[i]);
				if (it == target.end()) {
					target.push_back(s[i]);
				}
			}
		}
	}
	if (target.size() <= K - 5) {
		cout << N;
		return 0;
	}

	combi(-1, 0);
	cout << maxA;

}

/*
3 19
abcdefghijklmnopqrstuvwxyz
anticadd
anticfes

*/

 

비트마스킹을 활용한 코드 구현

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<math.h>
#include<map>

using namespace std;

int n, m, words[51];
string s;
int count(int mask) {
    int cnt = 0;
    //word && -> 0이 아닌 경우에만 검사
    for (int word : words) {
        if (word && (word & mask) == word)cnt++;
    }
    return cnt;
}

//비트마스킹과 재귀를 이용한 탐색
int go(int index, int k, int mask) {

    if (k < 0) return 0; //선택할 것이 없을 경우의 기저사례
    if (index == 26) return count(mask);   //끝까지 인덱스가 갔을 경우 세서 출력
    int ret = go(index + 1, k - 1, mask | (1 << index));
    
    //a, n, t, i, c는 항상 포함해야 한다.
    if (index != 'a' - 'a' && index != 'n' - 'a' && index != 't' - 'a' && index != 'i' - 'a' && index != 'c' - 'a') {
        ret = max(ret, go(index + 1, k, mask));  //최댓값 갱신
    }
    return ret;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> s;
        //abba -> 중복없이 넣기 가능
        for (char str : s) {
            words[i] |= (1 << (str - 'a'));
        }
    }
    cout << go(0, m, 0) << '\n';
    return 0;
}

 

 

코드를 이해하는데 한참 걸린 것 같다.

여러 코드를 보는 것이 실력 향상에 좋은 것 같다!