글 읽기 - 시간초과..

tjrwo3080 4년 전 0

어디서 시간초과가 나는걸까요..

#include <iostream>
using namespace std;

bool startTeam[21] = { false, };
int arr[21][21] = { 0, };
int N, maxTeamSize, sc, answer, sTeam, lTeam;


void calScore() {
	sTeam = 0, lTeam = 0;
	for (int i = 1; i < N; i++) {
		for (int j = i + 1; j <= N; j++) {
			if (startTeam[i] && startTeam[j]) {
				sTeam += (arr[i][j] + arr[j][i]);
			}
			else if (!startTeam[i] && !startTeam[j]) {
				lTeam += (arr[i][j] + arr[j][i]);
			}
		}
	}

	if(sTeam>lTeam)
		sc = sTeam - lTeam;
	else
		sc = lTeam - sTeam;

	if (sc < answer) {
		answer = sc;
	}
}

void dfs(int players) {
	if (players == maxTeamSize) {
		calScore();
		return;
	}
	else {
		for (int i = players + 1; i <= N; i++) {
			if (!startTeam[i]) {
				startTeam[i] = true;
				dfs(players + 1);
				startTeam[i] = false;
			}
		}
	}
}


void init() {
	cin >> N;
	maxTeamSize = N / 2;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> arr[i][j];
		}
	}
	answer = 10000;

	startTeam[1] = true;
	dfs(1);
	cout << answer << endl;
}


int main(void) {
	init();
	return 0;
}

ha_ram 4년 전 1

34번줄과 35번줄 사이에

for(int i=1; i<=N; i++){

if(startTeam[i]) printf("%d ",i);

}

printf("\n");

를 추가해 보시고 예제입력 2번째를 돌려보시면

중복되는 탐색을 하는게 보이실 겁니다.

중복탐색을 없애시면 될것같습니다.

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

문제

문제

출처

ICPC

시간초과..

tjrwo3080 4년 전 0

ha_ram 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말