글 읽기 - 시간초과 이유를 모르겠습니다.

marrin1101 4년 전 0

6% 진행하다가 시간초과가 뜹니다. 도와주세요 ㅠㅠ

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


int N;
vector<vector<int>> board;

// model --> 경우의수로 쓸 index
// depth --> N/2 횟수

int DFS(int depth, int model)
{
	if (depth == 0) {
		int scoreA = 0, scoreB = 0;
		vector<int> start, link;
		for (int i = 0; i < N; ++i)
		{
			if (model & (1 << i))
				start.push_back(i);
			else
				link.push_back(i);
		}

		for (int s = 0; s < start.size(); ++s)
			for (int t = s + 1; t < start.size(); ++t)
				scoreA += board[start[s]][start[t]] + board[start[t]][start[s]];

		for (int s = 0; s < link.size(); ++s)
			for (int t = s + 1; t < link.size(); ++t)
				scoreB += board[link[s]][link[t]] + board[link[t]][link[s]];

		return abs(scoreA - scoreB);
	}

	int ret = numeric_limits<int>::max();
	if (model == 0) {
		for (int i = 0; i < N; ++i)
			ret = min(ret, DFS(depth - 1, model | (1 << i)));
	}
	else {
		//unsigned long i = 0;
		//_BitScanForward(&i, model);
		//i++;
		for (int i = __builtin_ctz(model)+1; i < N; ++i)
			ret = min(ret, DFS(depth - 1, model | (1 << i)));
	}
	return ret;
}

void solve()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
	cin >> N;
	board = vector<vector<int>>(N, vector<int>(N, 0));
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			cin >> board[i][j];
	cout << DFS(N / 2, 0);
}

int main()
{
	solve();
	return 0;
}

inc5025 4년 전 1

팀원의 팀 분배가 적절하게 이루어지지 않으며, 같은 케이스를 두번 이상 계산하는 경우가 있습니다.

46번째 줄에서 model이 예를 들어 101100(2)일때, 오른쪽의 0의 갯수가 2개이니 i는 3부터 시작합니다.

다만 1 << 3인 8에 해당하는 비트는 이미 1이지만, 47번에서 이를 고려하지 않고 처리한 뒤, 다시 dfs를 돌게 됩니다.

marrin1101 4년 전 0

정말정말 감사합니다. 크게 도움이 되었습니다.

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

문제

문제

출처

ICPC

시간초과 이유를 모르겠습니다.

marrin1101 4년 전 0

inc5025 4년 전 1

marrin1101 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말