글 읽기 - 반례를 알려주실 수 있나요?

klm1118 4년 전 0

단어를 하나 씩 살펴보고 a,n,t,i,c 를 제외한 문자들만 모아서

가능한 최대 길이 만큼 조합을 만들어

초기 a,n,t,i,c 를 제외한 단어(initVector)모음에서 조합 별로 loop를 돌아 조합의 가장 큰 포함하는 문자의 수를 출력했는데..

어디서 잘못됬을까요..?

오래 고민하다가 질문드립니다..

질문 게시판의 반례는 모두 맞습니다.

도와주십쇼..

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

using namespace std;
int N, K, ans;
//조합 가능한 길이
int possibleLength;
vector<char> combiVector;
vector<vector<char>> combiStrVector;
//조합 재료
vector<string> initVector;
set<char> material;
vector<char> materialVector;

bool checkChar(const char c)
{
	if (c == 'a' || c == 'n' || c == 't' || c == 'i' || c == 'c')
	{
		return false;
	}
	return true;
}

void combination(int index)
{
	if (combiVector.size() >= possibleLength)
	{
		if (combiVector.size() == possibleLength)
		{
			combiStrVector.emplace_back(combiVector);
		}
	}
	else
	{
		for (int i = index; i < materialVector.size(); i++)
		{
			combiVector.emplace_back(materialVector[i]);
			combination(i + 1);
			combiVector.pop_back();
		}
	}
}

void Func()
{
	int tempAns = 0;
	set<string> total;
	for (const auto& d : combiStrVector)
	{
		string temp = "";
		for (auto z : d)
		{
			temp += z;
		}
		total.emplace(temp);
	}
	for (const auto& data : total)
	{
		int result = 0;
		for (int i = 0; i < initVector.size(); i++)
		{
			if (data.find(initVector[i]) != string::npos)
			{
				result++;
			}
		}
		tempAns = max(result, tempAns);
	}
	ans += tempAns;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> K;
	possibleLength = K - 5;
	if (K < 5)
	{
		cout << "0\n";
		return 0;
	}
	else if (K == 26) { cout << N << "\n"; return 0; }

		for (int i = 0; i < N; i++)
	{
		set<char> tempSet;
		string str = "";
		cin >> str;
		if (str.size() >= 8)
		{
			if (str.substr(0, 4) == "anta" && str.substr(str.size() - 4, 4) == "tica")
			{
				for (int i = 4; i < str.size(); i++)
				{
					if (checkChar(str[i]))
					{
						tempSet.emplace(str[i]);
					}
				}
				if (!tempSet.empty())
				{
					//최대로 가르칠 수 있는 글자의 수와 같거나 작아야한다.
					if (possibleLength >= tempSet.size())
					{
						for (const auto& d : tempSet) { material.emplace(d); }
						initVector.emplace_back(string(tempSet.begin(), tempSet.end()));
					}
				}
				//'a', 'n', 't', 'i', 'c'로 구성 가능한 경우
				else
				{
					ans++;
				}
			}
		}
	}
	materialVector = vector<char>(material.begin(), material.end());
	if (possibleLength > material.size())
	{
		possibleLength = material.size();
	}
	combination(0);
	for (auto d : combiStrVector) { for (auto z : d) { cout << z; }cout << " "; }
	Func();
	cout << ans << "\n";
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 알려주실 수 있나요?

klm1118 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말