글 읽기 - 시간초과 어떻게 해결할까요?

redball_var 6년 전 0

입력받은 문자열를 조합으로 뽑는 방식을 이용했습니다.

입력받은 문자 n개 중에 1개, 2개, ..., n개를 뽑았습니다.

그래서 만든 조합이 필랜드롬인지 체크했습니다.

그런데. 30C1 + 30C2 + 30C3 + ... + 30C30 이 10억이 좀 넘어서 시간초과가 납니다.

시간 줄이려고 필랜드롬이 아닌 경우는 가지치기를 해봤는데도 시간초과가 나네요..

어떻게 풀어야할지 감이 안오는데 힌트부탁드립니다.ㅠㅠ

#include <iostream>
using namespace std;

char print[31], freq[255];
char str[31];
int str_len;
int n, M; // M : 조합의 길이

// 조합을 만드는 함수
void make_set(int rs, int depth)
{
	if (depth == M)
	{
		++n;
		return;
	}

    // left : 필랜드롬인지 비교할 인덱스
	int mid = M / 2;
	int left;
	if (M % 2) left = mid - (depth - mid);
	else left = mid - (depth - mid) - 1;

	for (int s = rs; s < str_len; ++s)
	{
		if (freq[s]) continue;
		
		print[depth] = str[s];

        // 현재 위치와 비교 위치의 문자를 비교해 다르면 필랜드롬이 아니므로 pass.
		if (left < mid && print[depth] != print[left])
			continue;

		freq[s] = 1;
		make_set(s + 1, depth + 1);
		freq[s] = 0;
	}
}

int main()
{
	cin >> str;
	for (; str[str_len] != '\0'; ++str_len);
	n += str_len;

    // 입력받은 문자 n개 중에 2개, 3개, ..., n개를 뽑는 조합 만들기
	for (M = 2; M <= str_len; ++M)
		make_set(0, 0);
	cout << n << endl;

	return 0;
}

kkw564 6년 전 0

일단 접근자체가 아에 잘못된 것 같습니다.

30개의 문자열이면 최소 부분문자열이 ( 2^n )- 1개(공집합제외)인데 10억이면 10초입니다.

다른 알고리즘을 생각해보셔야 할 것같네요 구글링을 통해서 알고리즘을 공부하시는 것도 좋은 방법중 하나라고 생각합니다.

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

문제

문제

출처

ICPC

시간초과 어떻게 해결할까요?

redball_var 6년 전 0

kkw564 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말