글 읽기 - c++ 시간초과

s262 2년 전 0

백트레킹으로 선수를 뽑고 n/2명까지 뽑혔으면

각팀의 점수를 구해 최저차이값을 구했습니다..

점수를 구할때 2중 for문이 문제일까요?

어느부분을 최적화 해야되나요??

#include <iostream>
//#include <vector>
//#include <cmath>
//#include <algorithm>
#define endl '\n'

constexpr int LIMITE = 21;

using namespace std;

int n, MIN{ 100 }, input[LIMITE][LIMITE];
bool selected[LIMITE]{ 0, };
void test(int depth = 0);

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> input[i][j];
		}
	}

	test();
	cout << MIN << endl;

	return 0;
}

void test(int depth)
{
	if (depth == n / 2)
	{
		int sum{}, sum_a{}, sum_b{};
		for (int i = 1; i <= n; i++)
		{
			if (selected[i])
			{
				for (int j = 1; j <= n; j++)
				{
					if (selected[j])
					{
						sum_a += input[i][j];
					}
				}
			}
			else
			{
				for (int j = 1; j <= n; j++)
				{
					if (!selected[j])
					{
						sum_b += input[i][j];
					}
				}
			}
		}
		sum = (sum_a > sum_b ? sum_a - sum_b : sum_b - sum_a);
		if (sum < MIN) MIN = sum;
		return;
	}

	for (int i = 1; i <= n; i++)
	{
		if (!selected[i])
		{
			selected[i] = true;
			test(++depth);
			--depth;
			selected[i] = false;
		}
	}
}

s262 2년 전 0

재귀문에 idx를 추가하니 패스되네요..ㅠㅠ

이 작은게 속도차이가 어마 어마하군요...

	for (int i = idx; i <= n; i++)
	{
		if (!selected[i])
		{
			selected[i] = true;
			test(i, ++depth);
			--depth;
			selected[i] = false;
		}
	}

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

문제

문제

출처

ICPC

c++ 시간초과

s262 2년 전 0

s262 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말