글 읽기 - c++ 시간초과 질문

tinea17 3년 전 0

테케 다 통과하는데 시간초과가 납니다

어느 부분이 문제인지 봐주시면 감사드리겠습니다ㅠㅠ

백트래킹이랑 완전탐색 사용했습니다.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int s[21][21];
int start[11];
int link[11];
int min_result = 1e9;

void team(int n, vector<bool>& visited, int startidx, int linkidx, int cnt)
{
	if (cnt == n/2)
	{
		for (int i = 1; i <= n; i++)
		{
			if (!visited[i])
			{
				link[linkidx++] = i;
			}
		}

		// 각 팀의 능력치 계산하기
		int start_sum = 0;
		int link_sum = 0;
		for (int i = 0; i < n/2 - 1; i++)
		{
			for (int j = i+1; j < n/2; j++)
			{
				start_sum += s[start[i]-1][start[j]-1];
				start_sum += s[start[j]-1][start[i]-1];
				link_sum += s[link[i] - 1][link[j] - 1];
				link_sum += s[link[j] - 1][link[i] - 1];
			}
		}

		int result = abs(start_sum - link_sum);
		min_result = min(min_result, result);
		
		return;
	}

	for (int i = 1; i <= n; i++)
	{
		if (!visited[i])
		{
			start[startidx] = i;
			visited[i] = true;
			team(n, visited, startidx+1, linkidx, cnt+1);
			visited[i] = false;
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	vector<bool> visited(n+1, false);

	for (int i=0; i<n; i++)
		for (int j=0; j<n; j++)
			cin >> s[i][j];

	team(n, visited, 0, 0, 0);

	cout << min_result;
}

dlgldgld2 2년 전 0

1, 2, 3, 4, 5, 6 이나 6, 5, 4, 3, 2 ,1 은 같은 것이기 때문에 항상 N^N 만큼 수행이 되지 않아도 될 것 같습니다.

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

문제

문제

출처

ICPC

c++ 시간초과 질문

tinea17 3년 전 0

dlgldgld2 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말