글 읽기 - dfs를 통한 완전탐색으로 구현했는데 틀렸다고 나옵니다ㅜㅜ

hssk1528 5년 전 0

dfs로 완전탐색해서 n/2명이 되면 능력치 합 계산하도록 구현했습니다.

예시는 모두 맞는데 어느 경우에 틀리는지 모르겠습니다ㅠㅠ

도움 부탁드려요ㅠㅠㅠ

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

int n;
int cache[1 << 20];
int result = 987654321;
int s[10][10];  // 능력치

int calc_stats(int team, vector<int>& member) {
	// base case : 팀에 두명밖에 안남았다면 둘의 능력치를 계산함
	if (member.size() == 2) {
		return s[member[0]][member[1]] + s[member[1]][member[0]];
	}

	int& ret = cache[team];
	if (ret != 0) return ret;

	// 팀의 멤버 중 한명에 대해서 다른 멤버들과의 능력치 계산
	int one = member.back();
	member.pop_back();
	int plus = 0;
	for (int i = 0; i < member.size(); i++) {
		plus += (s[one][member[i]] + s[member[i]][one]);
	}

	team = team & ((1 << one) - 1);
	return ret = calc_stats(team, member) + plus;
}

void dfs(vector<int>& member, int st) {
	// n/2 명 조합이 완성되면 팀의 능력치 계산
	if (member.size() == n / 2) {
		vector<int> smember = member;
		vector<int> lmember;
		int start = 0;
		int link = 0;
		int pt = 0;

		for (int i = 0; i < n; i++) {
			if (pt < n / 2 && member[pt] == i) {
				start = start + (1 << i);
				pt++;
			}
			else {
				link = link + (1 << i);
				lmember.push_back(i);
			}
		}
		int res = abs(calc_stats(start, smember) - calc_stats(link, lmember));
		if (res < result) result = res;
		return;
	}

	for (int i = st; i < n; i++) {
		member.push_back(i);
		dfs(member, i + 1);
		member.pop_back();
	}
}

int main() {

	cin >> n;

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

	vector<int> temp = vector<int>();
	dfs(temp, 0);

	cout << result << endl;
	return 0;
}

hssk1528 5년 전 0

배열 s를 [20][20]으로 초기화했어야하는데 크기를 잘못넣었었네요ㅠㅠ

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

문제

문제

출처

ICPC

dfs를 통한 완전탐색으로 구현했는데 틀렸다고 나옵니다ㅜㅜ

hssk1528 5년 전 0

hssk1528 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말