글 읽기 - C++ 시간초과 문제

qwert232324 3년 전 0

DFS로 풀었는데, 다른분들의 코드와 비슷한 정도의 시간복잡도를 가지고 있는 것 같은데, 시작도 못하고 계속 시간초과가 걸리네요 ㅠㅠ 조언해주실분 계신가요

#include<iostream>
#include<algorithm>

using namespace std;

int N=0;
int uri = 0;
int sangdae = 0;
int MIN = 99999;
int used[20];
int team[20][20];

void BT(int num, int idx) {

	if (num == N / 2) {
		int uri_mem[10];
		int sangdae_mem[10];
		int uri_cnt = 0;
		int sangdae_cnt = 0;
		for (int i = 0; i < N; i++) {
			if (used[i] == 1) {
				uri_mem[uri_cnt] = i;
				uri_cnt++;
			}
			else {
				sangdae_mem[sangdae_cnt] = i;
				sangdae_cnt++;
			}
		}
		
		for (int i = 0; i < N / 2; i++) {
			for (int j = i + 1; j < N / 2; j++) {
				uri = uri + team[uri_mem[i]][uri_mem[j]] + team[uri_mem[j]][uri_mem[i]];
				sangdae = sangdae + team[sangdae_mem[i]][sangdae_mem[j]] + team[sangdae_mem[j]][sangdae_mem[i]];
			}
		}	

		if (abs(uri - sangdae) < MIN) MIN = abs(uri - sangdae);
		uri = 0;
		sangdae = 0;
		uri_cnt = 0;
		sangdae_cnt = 0;
		return;
	}
	for (int i = idx; i < N; i++) {
		if (used[i] == 1) continue;
		else{
			used[i]++;
			BT(num + 1,idx+1);
			used[i]--;
		}
	}
}


int main() {
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	
	cin >> N;
	for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> team[i][j];

	BT(0,0);
	cout << MIN;
}
	

tony9402 3년 전 1

49라인에 idx + 1이 아니라 현재 선택한 다음것부터 보면 되니깐 i + 1로 바꾸셔야할꺼에요

qwert232324 3년 전 1

감사합니다 해결했습니다!!!!! ㅠㅠㅠㅠㅠ

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

문제

문제

출처

ICPC

C++ 시간초과 문제

qwert232324 3년 전 0

tony9402 3년 전 1

qwert232324 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말