글 읽기 - 시간초과..

jeenee94 4년 전 0

먼저 anta, tica를 없애고 al배열에 이에 해당하는 알파벳을 체크한 뒤 백트래킹을 이용하여 풀었습니다.

최악의 경우 21C10 * 50 * 7 = 123,450,600으로, 1억이 넘어 이 방법으로는 풀 수 없는 건가요??

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

int n, k;
bool al[26];
string s[50];
int ans = 0;

void back_tracking(int x, int cnt) {
	if (cnt == k) {
		int tmp_ans = 0;
		for (int i = 0; i < n; ++i) {
			bool flag = true;
			for (int j = 0; j < s[i].length(); ++j) {
				if (!al[s[i][j] - 'a']) {
					flag = false;
					break;
				}
			}
			if (flag)
				tmp_ans++;
		}
		ans = max(ans, tmp_ans);
		return;
	}
	
	for (int i = x; i < 26; ++i) {
		if (al[i])
			continue;
		al[i] = 1;
		back_tracking(x+1, cnt+1);
		al[i] = 0;
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> k;
	
	if (k < 5) {
		cout << 0 << '\n';
		return 0;
	} else if (k == 26) {
		cout << n << '\n';
		return 0;
	}
	
	for (int i = 0; i < n; ++i) {
		cin >> s[i];
		s[i] = s[i].substr(4);
		for (int j = 0; j < 4; ++j) {
			s[i].pop_back();
		}
	}
	// "anta", "tica"
	al['a'-'a'] = al['c'-'a'] = al['i'-'a'] = al['n'-'a'] = al['t'-'a'] = 1;
	k -= 5;
	
	back_tracking(0, 0);
	
	cout << ans << '\n';
	
	return 0;
}

kimcoding 4년 전 3

배울 글자의 경우를 구할 때 예를 들어 BDEF와 중복이 되는 BDFE, BEDF, BEFD, BFDE ... 등의 경우까지 다 봐주게 됩니다.

34번 줄에서 인자를 i + 1를 하려고 하신것 같은데 실수 하신것 같네요.

jeenee94 4년 전 0

아.. 제가 제대로 못봤나보네요..ㅠ 감사합니다. 바로 통과되네요!

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

문제

문제

출처

ICPC

시간초과..

jeenee94 4년 전 0

kimcoding 4년 전 3

jeenee94 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말