글 읽기 - 63~64퍼에서 자꾸 시간초과라는데...

gomyk12 7년 전 0

도저히 이유를 모르겠습니다. 모든 테스트를 만들어서 해봐도 2초 이상 오래걸릴 일이 전혀 없는데 혹시 이 문제를 푸셨거나 어떤 경우에서 시간초과가 나는지 아시는 분은 답편 부탁드립니다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int min_count = 9999;
int N;
int result_min = 9999;

string str;
string *word;
string *sorted_word;
int go(string result,int result_count,int position) {
	int result_length = result.length();
	if (result_min < result_count) {
		return 0;
	}
	if (result_min == 0) {
		return 0;
	}
	bool next = false;
	if (result_length < min_count) {
		if (result_length == 0) {
			if (result_min > result_count) {
				result_min = result_count;
			}
			return 0;
		}
		else {
			return 0;
		}
	}
	else {
		
		int leng = 0;
		int before_length = 0;
		int min_n = 999;
		for (int n = 0; n < N; n++) {
			
			if (word[n] == ".") {

			}
			else {
				int word_length;
				word_length = word[n].length();
				if (word_length != before_length) {
					before_length = word_length;
					min_n = 999;
				}
				if (result_length < word_length) {
					return 0;
				}

				string tm;
				string sort_tm;

				int temp_count = 0;
				int dif_count = 0;
				tm = result.substr(0, word_length);
				sort_tm = tm;
				sort(&sort_tm[0], &sort_tm[0] + word_length);
				//
				if (sort_tm == sorted_word[n]) {
					next = true;
					for (int k = 0; k < word_length; k++) {
						if (word[n][k] != tm[k]) {
							dif_count++;
						}
					}
					if (dif_count < min_n) {
						go(result.substr(word_length), result_count + dif_count, position + word_length);
					}
				}
			}
		}
	}
	if (!next) {
		return 0;
	}
}

int main() {

	bool ok = true;
	cin >> str;
	cin >> N;
	word = new string[N];
	sorted_word = new string[N];
	for (int i = 0; i < N; i++) {
		cin >> word[i];
		sorted_word[i] = word[i];
	}

	
	for (int i = 0; i < N; i++) {
		if (word[i].length() < min_count) {
			min_count = word[i].length();
		}
	}//50번

	for (int i = 0; i < N; i++) {
		for (int j = i+1; j < N; j++) {
			if (word[i].length() > word[j].length()) {
				string temp;
				temp = word[j];
				word[j] = word[i];
				word[i] = temp;
			}
		}
	}//버블 정렬
	for (int i = 0; i < N; i++) {
		sorted_word[i] = word[i];
		sort(&sorted_word[i][0], &sorted_word[i][0] + sorted_word[i].length());
	}
	for (int i = 0; i < N; i++) {
		for (int j =i+1; j < N; j++) {
			if (word[i] == word[j]) {
				word[j] = ".";
				sorted_word[j] = ".";
			}
		}
	}
	string sub;
	int total_length = str.length();
	int word_leng;
	bool ok_c = false;
	for (int i = 0; i < total_length; i++) {
		for (int j = 0; j < N; j++) {
			word_leng = sorted_word[j].length();
			if (i < total_length - word_leng + 1) {
				sub = str.substr(i, sorted_word[j].length());
				sort(&sub[0], &sub[0] + word_leng);
				if (sorted_word[j] == sub) {
					ok_c = true;
					break;
				}
			}
			else {
				break;
			}
		}
	}
	if (!ok_c) {
		cout << -1 << endl;
		return 0;
	}
	if (!ok) {
		cout << -1 << endl;
		return 0;
	}
	string result = str;
	go(result,0,0);
	if (result_min != 9999) {
		cout << result_min << endl;
	}
	else {
		cout << -1 << endl;
	}
	return 0;
}

doju 7년 전 0

데이터 하나 드립니다.

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
50
a
aa
aaa
aaaa
aaaaa
aaaaaa
aaaaaaa
aaaaaaaa
aaaaaaaaa
aaaaaaaaaa
aaaaaaaaaaa
aaaaaaaaaaaa
aaaaaaaaaaaaa
aaaaaaaaaaaaaa
aaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

gomyk12 7년 전 0

불가능한 경우를 찾는 코드를 추가해서 위와같은 케이스는 통과시켰는데도

64퍼에서 정확하게 시간초과가 뜨네요 ㅜㅜ

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

문제

문제

출처

ICPC

63~64퍼에서 자꾸 시간초과라는데...

gomyk12 7년 전 0

doju 7년 전 0

gomyk12 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말