백준 [1062] "가르침"

Kimbab1004·2024년 8월 23일
0

Algorithm

목록 보기
77/102

오답

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


using namespace std;

int n = 0;
int k = 0;
int result = 0;

//추가 처리
vector<char> c;

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

	cin >> n >> k;

	vector<pair<int,string>> v(n);

	for (int i = 0; i < n; i++) {
		string a;
		cin >> a;
		//a n t i c 
		for (int j = 0; j < a.size(); j++) {
			if (a[j] != 'a' && a[j] != 'n' && a[j] != 't' && a[j] != 'i' && a[j] != 'c') {
				v[i].first += 1;
				v[i].second.push_back(a[j]);
			}
		}
	}

	if (k < 5) {
		cout << 0;
		return 0;
	}

	k -= 5;

	sort(v.begin(), v.end());

	for (int i = 0; i < v.size(); i++) {

		int count = 0;

		for (int z = 0; z < v[i].second.size(); z++) {
			for (int x = 0; x < c.size(); x++) {
				//만약 현재 단어가 추가 처리에 있을 경우
				if (v[i].second[z] == c[x]) {
					count++;
				}
			}
		}
		v[i].first -= count;

		if (k - v[i].first >= 0 ) {
			//정답 추가
			result++;
			k -= v[i].first;
			//추가 처리에 현재 답 추가
			for (int z = 0; z < v[i].second.size(); z++) {
				int flag = 1;
				for (int u = 0; u < c.size(); u++) {
					if (v[i].second[z] == c[u]) {
						flag = 0;
					}
				}
				if (flag == 1) {
					c.push_back(v[i].second[z]);
				}
			}
		}
		
		else {
			break;
		}
	}

	cout << result;

	return 0;
}

정답 출처

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

using namespace std;

int n = 0;
int k = 0;
int result = 0;

//추가 처리
vector<string> v;

bool alpha[26] = { false };

void backtracking(int idx, int cur) {
	if (cur == 0) {
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			int flag = 1;
			for (int j = 0; j < v[i].size(); j++) {
				if (!alpha[v[i][j] - 'a']) {
					flag = 0;
					break;
				}
			}
			if (flag) {
				cnt++;
			}
		}
		result = max(result, cnt);
		if (result == n) {
			cout << result;
			exit(0);
		}
		return;
	}
	for (int i = idx; i < 26; i++) {
		if (alpha[i]) continue;
		alpha[i] = true;
		backtracking(i, cur - 1);
		alpha[i] = false;
	}
}

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

	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		v.push_back(s.substr(4, s.length() - 8));
	}

	if (k - 5 < 0) {
		cout << 0;
		return 0;
	}

	//a n t i c 
	alpha['a' - 'a'] = true;
	alpha['n' - 'a'] = true;
	alpha['t' - 'a'] = true;
	alpha['i' - 'a'] = true;
	alpha['c' - 'a'] = true;

	backtracking(0, k - 5);
	cout << result;

	return 0;
}

0개의 댓글