1062번: 가르침

Memo

어려웠던 점

K가 만약에 10 이라고 한다면, 21C10 = 352716 이고 (5개의 알파벳은 이미 확정적이므로 21임) N의 최대값인 50과 길이의 최대값인 7 (양 옆을 제거하면 7이 최대) 을 모두 곱하면 123450600(1억이 넘음) 이라는 숫자가 나오는데, 이는 1초만에 계산을 끝낼 수 있는 연산량이 아니라고 생각이 들었기 때문에 코드를 작성하기 망설여 졌습니다.

우선 1억 언저리 이므로 코드를 작성해 봅니다.

처음 시간 초과가 났던 코드

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

std::vector<std::string> words;
std::vector<int> check;
int N, K, ans;

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

int alpha_to_index(char ch)
{
	return (ch - 'a');
}

void input()
{
	input_faster();
	std::cin >> N >> K;
	words.resize(N);
	size_t _N = N;
	for (size_t i = 0 ; i < _N ; i++)
		std::cin >> words[i];
	check.resize(26, 0);
	ans = 0;
	check[0] = 1;
	check[2] = 1;
	check[8] = 1;
	check[13] = 1;
	check[19] = 1;

}

std::string parsing(std::string a)
{
	std::string rtn;
	for (size_t i = 4 ; i < a.size() - 4; i++)
		rtn.push_back(a[i]);
	return (rtn);
}

int main_logic()
{
	size_t cnt;
	int rtn = 0;

	for (size_t i = 0 ; i < N ; i++)
	{
		cnt = 0;
		for (size_t j = 0 ; j < words[i].size(); j++)
		{
			if (!(check[alpha_to_index(words[i][j])]))
				break;
			cnt++;
		}
		if (cnt == words[i].size())
			rtn++;
	}
	return (rtn);
}

void backtracking(int depth)
{
	if (depth == K)
	{
		int val = main_logic();
		ans = std::max(val, ans);
		return ;
	}
	for (size_t i = 0 ; i < 26 ; i++)
	{
		if (!check[i])
		{
			check[i] = 1;
			backtracking(depth + 1);
			check[i] = 0;
		}
	}
}

void solve()
{
	if (K < 5)
		return ;
	K -= 5;
	for (size_t i = 0 ; i < words.size(); i++)
		words[i] = parsing(words[i]);
	backtracking(0);
}

void print_val()
{
	std::cout << ans;
}

int main()
{
	input();
	solve();
	print_val();
	return (0);
}

위 코드의 문제점은

for (size_t i = 0 ; i < 26 ; i++)
	{
		if (!check[i])
		{
			check[i] = 1;
			backtracking(depth + 1);
			check[i] = 0;
		}

바로 이 부분이었는데, 이 코드의 경우는 예를 들어 BCD, BDC를 각각의 경우로 계산한다는 점이었습니다. 따라서 이는 조합 코드가 아니기 때문에 코드를 다음과 같이 수정했습니다.

for (size_t i = x ; i < 26 ; i++)
	{
		if (!check[i])
		{
			check[i] = 1;
			backtracking(i + 1, depth + 1);
			check[i] = 0;
		}
	}

Code