글 읽기 - 시간초과가 자꾸나는데

gudrkrsla 5년 전 0

dfs를 이용한 완전탐색으로 했는데...add함수가 문제인 걸까요..?

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> sub;
int start[10];
int link[10];
int Sub=0;
int N;
int S[20][20];
int Count = 0;
bool visited[20];
int add(int *t) {  //팀의 전체 에너지를 구함 n*n-n번
	int sum = 0;
	for (int i = 0; i < N/2; i++) {
		for (int j = 0; j < N/2; j++) {
			if (i == j)continue;
			sum += S[t[i]][t[j]];
		}
	}
	return sum;
}

void dfs(int p) {
	if (Count == N / 2) { //스타트 팀에 절반만큼 들어가면 자동으로 링크팀을 배정하여 각 팀의 에너지를 더한후 빼준뒤, sub 벡터에 push
		for (int i = 0,j=0; i < N; i++)
			if (visited[i] == false) {
				link[j] = i;
				j++;
			}
		sub.push_back(abs(add(start)-add(link)));
		return;
	}
	for (int i = p; i < N; i++) { //완전탐색
		if (visited[i] == false) {
			visited[i] = true;
			start[Count] = i;
			Count++;
			dfs(i);
			visited[i] = false;
			Count--;
			dfs(i + 1);
		}
	}
}
int main() {
	scanf_s("%d", &N);
	for (int y = 0; y < N; y++)
		for (int x = 0; x < N; x++)
			scanf_s("%d", &S[y][x]);
	dfs(0);
	sort(sub.begin(), sub.end());
	printf("%d", sub[0]);
	return 0;
}

djm03178 5년 전 0

scanf_s를 scanf로 바꾼 건 가정하고, 42번째 줄만 지우면 맞습니다.

gudrkrsla 5년 전 0

아...바보같은 실수를 했네요...감사합니다!!

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

문제

문제

출처

ICPC

시간초과가 자꾸나는데

gudrkrsla 5년 전 0

djm03178 5년 전 0

gudrkrsla 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말