글 읽기 - 시간복잡도를 어떻게 줄일수있을까요?

jow1025 4년 전 0

백트래킹을 이용해서 cnt=n/2가 되면

check한 사람들과 check하지않은 사람들 두 그룹으로 나누어 하나씩 비교해보는건데,

다른 잘푸신분들은 60~100ms 내외로 나오시던데 저는 200ms가 나오더라구요.

풀이도 비슷한거같은데 어느부분에서 시간을 줄일수있을까요?

#include<iostream>
using namespace std;
int map[20][20];
bool check[20];
int max_val = 10001;
int n;
void dfs(int cnt, int pos);
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];
	dfs(0, 0);
	cout << max_val << '\n';
}
void dfs(int cnt, int pos)
{
	if (cnt == n / 2)
	{
		int start = 0, link = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (i == j)continue;
				if (check[i] && check[j])start += map[i][j];
				if (!check[i] && !check[j])link += map[i][j];
			}
		}
		int val = abs(start - link);
		if (val < max_val)max_val = val;
		return;
	}
	for (int i = pos; i < n; i++)
	{
		check[i] = true;
		dfs(cnt + 1, i + 1);
		check[i] = false;
	}
}

palatable7 4년 전 0

28~30 줄에서

if(i==j)부분 제거 하시고

그 밑에 두 줄을 if와 else if로 놓으면 어떨까요?

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

문제

문제

출처

ICPC

시간복잡도를 어떻게 줄일수있을까요?

jow1025 4년 전 0

palatable7 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말