글 읽기 - 가르침 - 백트래킹 시간초과의 이유를 모르겠습니다.

shy817 6년 전 0

1. 5% 쯤에서 시간초과가 납니다.

2. 처음에 입력받으면서 antic, 한 단어안에서 중복되는 문자 제거 했고 k-5에 대해 백트래킹 하였습니다.

==> 백트래킹 후보군 줄인다고 줄였는데 어디서 시간초과가 나는걸까요?

거르지 못한 조건이 있을까요?

혹시 잘못짜서 무한 루프 도는 경우가 있을까요?

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

int maxRes;
int maxK;

//완전 탐색하는 dfs 함수
//k는 배울 수 있는 남은 글자의 수
//idx는 alphabet에서 배울 글자의 인덱스
//alphabet 은 배워야하는 글자의 종류
//words는 읽어야하는 단어들
//문자 하나 배우면 -> words에서 지우고 읽을 수 있는 문자의 수 세기
//문자의 수 는 max값으로 갱신

void DFS(int k, int idx, string alphabet, vector<string> words) {
	//더 배울 문자가 없으면 리턴
	if (k == 0) {
		return;
	}

	//배울 문자
	char ch = alphabet[idx];

	//글자 지우기
	int len = words.size();
	int cnt = 0;
	for (int i = 0; i < len; i++) {
		//현재 단어
		string word = words[i];
		//새로운 단어
		string newWord = "";
		
		//배운 단어ch 이면 통과하고 아닌 단어만 남겨서 새로운 newWord를 만든다.
		int size = word.size();
		for (int j = 0; j < size; j++) {
			if (word[j] == ch) continue;
			newWord += word[j];
		}

		//newWord로 word를 갱신
		words[i] = newWord;

		//읽을 수 있는 문자가 되었나?
		if (newWord.size() == 0) cnt++;
	}

	//기존보다 더 많이 읽을 수 있게 되었으면 max 갱신
	if (cnt > maxRes) {
		maxRes = cnt;
	}

	//다른 문자 배우기
	//현재 문자 이후의 것으로 고름
	//남은 문자의 갯수는 전체갯수 - (총 배워야할 갯수 - 남은 배워야할 갯수 = 이미 배운 갯수)
	int length = alphabet.size() - (maxK-k);
	for (int next = idx + 1; next < alphabet.size(); next++) {
		DFS(k-1, next, alphabet, words);
	}
}

int main() {

	int n, k;
	cin >> n >> k;

	maxK = k;
	//기본 적으로 a n t i c 5개를 가르칠 수 있어야 한다.
	if (k < 5) cout << 0;

	vector<string> v;
	string alph = "";
	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;

		//anta~tica는 빼고 저장
		int len = str.size();
		str = str.substr(4, len-8);
		
		//a n t i c도 빼고 저장
		//한 단어에서 중복되는 것은 하나만 저장
		len = str.size();
		string newChar = "";
		for (int s = 0; s < len; s++) {
			
			if (str[s] == 'a' || str[s] == 'n' || str[s] == 't' || str[s] == 'i' || str[s] == 'c') continue;
			if (newChar.find(str[s]) != string::npos) continue;
			newChar += str[s];

			//배워야하는 글자 목록에 없으면 추가
			if (alph.find(str[s]) == string::npos) {
				alph += str[s];
			}
		}

		//cout << newChar << endl;
		v.push_back(newChar);
	}
    
	//dfs를 시작할 첫 글자 선택 - alph에 있는 글자들이 한번씩 다 선택된다.
	int dfs_size = alph.size();
	for (int next = 0; next < dfs_size; next++) {
		DFS(k-5, next, alph, v);
	}

	cout << maxRes;

	return 0;
}

chogahui05 6년 전 0

백트래킹 후보군 줄여버리는 건 맞고요.

제가 봤을 땐..

17번째 인자 넘기는 게 문제인 거 같네요. 벡터를 통째로 넘기시면 시간초과 나기 딱 좋죠..

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

문제

문제

출처

ICPC

가르침 - 백트래킹 시간초과의 이유를 모르겠습니다.

shy817 6년 전 0

chogahui05 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말