글 읽기 - [C]시간초과

sungweni 4년 전 0

도대체 어디서 시간초과가 나는 걸까요 ㅠㅠ

채점 진행조차 안합니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

int S_ij[20][20] = { 0 };
int Member_Start[10] = { 0 };
int Member_Link[10] = { 0 };
int visited[20] = { 0 };
int Gap = 2147483647;

void ReadN_Point(int* N, int S_ij[][20])
{
	scanf("%d", N);

	int i, j;

	for (i = 0; i < *N; i++)
	{
		for (j = 0; j < *N; j++)
		{
			scanf("%d", &S_ij[i][j]);
		}
	}
}

//중복수열을 제외하기 위한 함수.
bool isOrdered(int size, int arr[])
{
	int i;

	for (i = 0; i < size - 1; i++)
	{
		if (arr[i] > arr[i+1])
			return false;
	}

	return true;
}

int CalculateAbilityOfTeam_Start(int N)
{
	int Ability = 0;

	int i, j;


	for (i = 0; i < N / 2; i++)
	{
		for (j = 0; j < N / 2; j++)
		{
			Ability += S_ij[Member_Start[i]][Member_Start[j]];
		}
	}

	return Ability;
}

int CalculateAbilityOfTeam_Link(int N)
{
	int Ability = 0;

	int i, j;


	for (i = 0; i < N / 2; i++)
	{
		for (j = 0; j < N / 2; j++)
		{
			Ability += S_ij[Member_Link[i]][Member_Link[j]];
		}
	}

	return Ability;
}

void PickMembers(int N, int depth)
{
	int i;
	int idx = 0;

	if (depth == N / 2)
	{
		//나머지 멤버 채워넣기
		if (isOrdered(N / 2, Member_Start))
		{
			for (i = 0; i < N; i++)
			{
				if (visited[i] == 0)
				{
					Member_Link[idx++] = i;
				}
			}
		}

		if (Gap > abs(CalculateAbilityOfTeam_Start(N) - CalculateAbilityOfTeam_Link(N)))
			Gap = abs(CalculateAbilityOfTeam_Start(N) - CalculateAbilityOfTeam_Link(N));
		return;
	}

	for (i = 0; i < N; i++)
	{
		if (visited[i] == 0)
		{
			visited[i] = 1;
			Member_Start[depth] = i;
			PickMembers(N, depth + 1);
			visited[i] = 0;
		}
	}
}

int main()
{
	int N = 0;

	ReadN_Point(&N, S_ij);
	PickMembers(N, 0);
	printf("%d", Gap);

	return 0;
}

snrnsidy 4년 전 0

N=20인 케이스에 대해서 시간초과가 나옵니다.

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

문제

문제

출처

ICPC

[C]시간초과

sungweni 4년 전 0

snrnsidy 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말