[성실코딩 1일차] 백준 #14889 스타트와 링크

일단! 새해부터 다시 열심히 하기로 마음가짐을 다잡았으니

1일차로 카운트를 시작했당

두번째! 스타트와링크 코테 처음 공부할 때 풀어봤던 문제다. 그 때 못풀어서 다른 코드 보면서 공부했었는데 

이번에는 쉽게 풀었다. 대신 똑같은 구조? 방식으로 풀어낸 것 같다.

#include < iostream >

using namespace std;

#define INF 987654321

int N;
int s[20][20];
int people[20] = { 0, };

int minValue = INF;

bool countTeam() {
	int cnt[2] = { 0,0 };
	for (int i = 0; i < N; i++) {
		if (people[i]==0) {
			cnt[0]++;
		}
		else {
			cnt[1]++;
		}
	}
	if (cnt[0] == N / 2 && cnt[1] == N / 2) { // 스타트, 링크 팀 각각 N/2 명
		return true;
	}
	return false;
}

int getDiff() {
	int cnt[2] = { 0,0 };
	for (int i = 0; i < N; i++) {
		int teamOfI = people[i];
		for (int j = 0; j < N; j++) {
			if (i == j) {
				continue;
			}
			if (teamOfI == people[j]) {
				cnt[teamOfI] += s[i][j];
			}
		}
	}
	int diff = cnt[0] - cnt[1];
	if (diff < 0) { // 음수를 절대값 처리
		return -diff;
	}
	return diff;
}

void divideTeam(int _idx) {
	if (_idx == N - 1) { // 탈출 조건
		// 1. 스타트, 링크 팀 각각 N/2명인지 확인
		// 아닐경우 return
		if (countTeam() == true) {
			// 스타트, 링크 팁 능력치 계산
			// 최소값으로 업데이트
			int value = getDiff();
			if (value < minValue) {
				minValue = value;
			}
		}
		return;
	}
	people[_idx] = 0;
	divideTeam(_idx + 1);
	people[_idx] = 1;
	divideTeam(_idx + 1);
}

int main(void) {

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

	divideTeam(0);

	cout << minValue << endl;

	return 0;
}