글 읽기 - 이런식으로 짜면 시간초과가 발생해야하지 않나요?

olbbemi 6년 전 1

정답유출 방지를 위해서 핵심코드는 다 제거했고 의문점이 드는 곳만 남겨두었습니다.

이 문제를 저는 순열을 이용하여 완전탐색을 실행했는데 N개 중에 절반은 0으로 절반은 1로 초기화한 뒤 이를 next_permutation 으로 돌렸습니다.

주어진 수의 범위가 1 ~ 100이라면 시간조과가 발생하는게 맞지 않나 싶습니다만 아무런 문제 없이 답이 나와서 질문드려봅니다.

int main()
{
	int N, result = INF;
	scanf("%d", &N);
	vector<int> v(N + 1), Info(N + 1, 1);
	for (int i = 1; i <= N; i++)
		v[i] = i;

	for (int i = 1; i <= N / 2; i++)
		Info[i] = 0;

	int k = 0;
	do
	{
		k++;
		

	} while (next_permutation(Info.begin() + 1, Info.end()));

	printf("\nK : %d\n", k);
	printf("%d", result);
	return 0;
}

ho94949 6년 전 0

그래서 계산한 시간복잡도가 어떻게 되나요?

olbbemi 6년 전 0

N! 아닌가요?

chogahui05 6년 전 0

20C10 * 400 정도 될 건데요. 최악의 경우에 20개중 10개는 1을 놓아야 하니까요.

20C10 = 184756이네요. naive하게 돌리면 x400

시간 초과 안 날 거 같은데요.

olbbemi 6년 전 0

아.. 잘못봣네요 ㅎㅎ N 이 20이엿구나. N 의 범위가 100이라는줄알앗네요.

감사합니다.

orslow 5년 전 0

절반은 0, 절반은 1로 해서 next_permutation 돌린다는 방법이 감탄스럽네요. 덕분에 한수 배우고 갑니다 고맙습니다.

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

문제

문제

출처

ICPC

이런식으로 짜면 시간초과가 발생해야하지 않나요?

olbbemi 6년 전 1

ho94949 6년 전 0

olbbemi 6년 전 0

chogahui05 6년 전 0

olbbemi 6년 전 0

orslow 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말