[BAEKJOON] 14889번 스타트와 링크

문 제

 

소 스  코 드

#include <iostream>
#include <cmath>

void Func(const int&, const int&, const int&, bool *, int **);

int min_number	{ 1'000'000'000 };

int arr[4];

int main() {

	int N;

	std::cin >> N;

	if (!(4 <= N && N <= 20))		return 0;
	if (1 == (N % 2))			return 0;

	int **temp				{ new int*[N] };
	bool * temp_tf				{ new bool[N] };

	for (int i = 0; i < N; ++i) {
		temp[i] = new int[N];
		temp_tf[i] = false;
	}
	
	
	
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			std::cin >> temp[i][j];
		}
	}

	Func(0, N, 0, temp_tf, temp);

	std::cout << min_number;

	// delete
	for (int i = 0; i < N; ++i) delete[] temp[i];
	delete[] temp;
	delete[] temp_tf;

	return 0;
}


void Func(const int& count, const int& N, const int& start, bool * temp_tf, int ** temp) {
	// if (1 == seq_arr[(N / 2)]) return; // 스타트팀과 링크팀 중복 제거

	if (count == N / 2) {
		int first_temp{ 0 };
		int second_temp{ 0 };

		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if ((false == temp_tf[i]) && (false == temp_tf[j]))
					second_temp += temp[i][j];
				else if ((true == temp_tf[i]) && (true == temp_tf[j])) 
					first_temp += temp[i][j];
			}
		}

		int minus_temp{ abs(first_temp - second_temp) };

		if (min_number > minus_temp) min_number = minus_temp;

		return;
	}


	for (int i = start; i < N; ++i) {
		if (true == temp_tf[i]) continue;

		temp_tf[i] = true;

		arr[count] = i + 1;
		Func(count + 1, N, i + 1, temp_tf, temp);
		temp_tf[i] = false;
	}
}

 

풀 이

 

• N / 2 개 씩 나뉜 2개의 스타트 팀과 링크 팀이 존재하는데, 스타트 팀만 구해도 링크 팀은 중복을 제외한 수가 구해지기 때문에 N명 중에 N / 2를 구하는 백트래킹 재귀 호출을 통한 구현을 하였습니다.

• Count 가 N / 2과 같아 질 경우 true는 스타트팀 멤버 false는 링크 팀 멤버이기 때문에 2중 for문을 통한 순회를 하여 값을 구한 후 두 팀 간의 차이의 최솟값을 구할 수 있었습니다.

 

실 수 했 던  사 항

#include <iostream>
#include <cmath>

void Func(const int&, const int&, const int&, bool *, int *, int **);

int min_number	{ 1'000'000'000 };

int main() {

	int N;

	std::cin >> N;

	if (!(4 <= N && N <= 20))		return 0;
	if (1 == (N % 2))			return 0;

	int **temp				{ new int*[N] };
	bool * temp_tf				{ new bool[N] };

	int  *seq_arr				{ new int[N] };

	for (int i = 0; i < N; ++i) {
		temp[i] = new int[N];
		temp_tf[i] = false;
	}
	
	
	
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			std::cin >> temp[i][j];
		}
	}

	Func(0, N, 0, temp_tf, seq_arr, temp);

	std::cout << min_number;

	// delete
	for (int i = 0; i < N; ++i) delete[] temp[i];
	delete[] temp;
	delete[] temp_tf;
	delete[] seq_arr;

	return 0;
}


void Func(const int& count, const int& N, const int& start, bool * temp_tf, int * seq_arr, int ** temp) {
	if (1 == seq_arr[(N / 2)]) return; // 스타트팀과 링크팀 중복 제거

	if (count == N) {
		int first_temp{ 0 };
		int second_temp{ 0 };
		
		for (int i = 0; i < (N / 2); ++i) {
			for (int j = 0; j < (N / 2); ++j) {
				first_temp += temp[seq_arr[i]][seq_arr[j]];
			}
		}

		for (int i = (N / 2); i < N; ++i) {
			for (int j = (N / 2); j < N; ++j) {
				second_temp += temp[seq_arr[i]][seq_arr[j]];
			}
		}

		int minus_temp{ abs(first_temp - second_temp) };

		if (min_number > minus_temp) min_number = minus_temp;

		return;
	}
	
	int nstart			{ start };

	if (0 == (count % (N / 2))) nstart = 0;


	for (int i = nstart; i < N; ++i) {
		if (true == temp_tf[i]) continue;
		
		temp_tf[i] = true;

		seq_arr[count] = i;
		Func(count + 1, N, i + 1, temp_tf, seq_arr, temp);

		temp_tf[i] = false;
	}


}

• N 개 중에 N / 2 스타트 멤버만 구해도 되는 문제 였지만 스타트 팀과 링크 팀을 합한 N개를 구하려고 하여 문제의 정답은 맞았지만 실행 속도에 차이가 있었습니다.
  if문에 % / 을 계산을 계속 해줘야하기 때문에 속도 차이가 발생.

결 과 값

 

 

문 제  출 처

문제 링크 : [ BAEKJOON ] https://www.acmicpc.net/problem/14889