[백준 14889] 스타트와 링크

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

#include <cstdio>
#include <cstdlib>
#include <vector>
int N;
int A[20 + 2][20 + 2];	// 능력치
int ans = 0x7fffffff;

std::vector<int> S;	// 스타트 팀
std::vector<int> L;	// 링크 팀


void input()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &A[i][j]);
		}
	}
}


int get_ability(std::vector<int> Team)
{
	int total = 0;
	for (int t1 : Team) {
		for (int t2 : Team) {
			total += A[t1][t2];
		}
	}
	return total;
}



void DFS(int n, int start, int link)
{
	if (start > N / 2 || link > N / 2) return;

	if (start == N / 2 && link == N / 2) {
		int steam = get_ability(S);
		int lteam = get_ability(L);
		int score = abs(steam - lteam);
		if (ans > score) ans = score;
		return;
	}

	if (n == N) return;

	// start 팀
	S.push_back(n);
	DFS(n + 1, start + 1, link);
	S.pop_back();

	// link 팀
	L.push_back(n);
	DFS(n + 1, start, link + 1);
	L.pop_back();
}

int main()
{
	input();
	DFS(0, 0, 0);
	printf("%d\n", ans);
	return 0;
}

 

 

스타트와 링크를 스근하게 풀었다면 ? => 링크와 스타트도 풀어보기 !

[백준 15661] 링크와 스타트

https://www.acmicpc.net/problem/15661

15661번: 링크와 스타트

#include <cstdio>
#include <cstdlib>
#include <vector>
int N;
int A[20 + 2][20 + 2];
int ans = 0x7fffffff;

std::vector<int> S;
std::vector<int> L;

void input()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &A[i][j]);
		}
	}
}


int get_ability(std::vector<int> Team)
{
	int total = 0;
	for (int t1 : Team) {
		for (int t2 : Team) {
			total += A[t1][t2];
		}
	}
	return total;
}


void DFS(int n, int start, int link)
{
	if (start > N || link > N) return;

	if (start >= 1 && link >= 1 && start + link == N) {
		int team1 = get_ability(S);
		int team2 = get_ability(L);
		int score = abs(team1 - team2);
		if (ans > score) ans = score;
		return;
	}

	if (n == N) return;

	S.push_back(n);
	DFS(n + 1, start + 1, link);
	S.pop_back();

	L.push_back(n);
	DFS(n + 1, start, link + 1);
	L.pop_back();
}



int main()
{
	input();
	DFS(0, 0, 0);
	printf("%d\n", ans);
	return 0;
}

 

---

배열로 푼 이전풀이...

#include <stdio.h>
#include <stdlib.h>
int N;
int ability[20 + 10][20 + 10];	//입력받는 능력치
int combi[1000000][10 + 10];		//조합의 경우의 수
int numbers[20 + 10];	//1부터 20까지의 수
int flag[20 + 10];		//조합 만들때 방문 여부
int num;	//조합의 개수

void input(void)
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &ability[i][j]);
		}
	}
}

void team_combi(int n, int r)	//조합 경우의 수 구하기
{
	if (n == N / 2) {
		for (int i = 0; i < N / 2; i++) {
			combi[num][i] = numbers[i];
			//printf("%d ", combi[num][i]);
		}
		num++;
		//printf("\n");
	}
	for (int i = r; i < N; i++) {
		if (flag[i] == 0) {
			numbers[n] = i + 1;
			flag[i] = 1;
			team_combi(n + 1, i);
			flag[i] = 0;
		}
	}
}


int total_ability(int a)	//팀의 능력치 구하기 
{
	int tmp = 0;
	for (int i = 0; i < (N / 2) - 1; i++) {
		for (int j = i + 1; j < N / 2; j++) {
			int t1 = combi[a][i] - 1;
			int t2 = combi[a][j] - 1;
			tmp += ability[t1][t2];
			tmp += ability[t2][t1];
			//printf("a : %d combi[a][i] : %d combi[a][j] : %d tmp : %d\n",a, combi[a][i], combi[a][j], tmp);
		}
	}
	return tmp;
}


int get_min(void)	//각 팀의 능력치의 차를 구하여 최솟값 알아내기
{
	int min = 0x7fffffff;
	for (int i = 0; i < num / 2; i++) {
		int start = 0; int link = 0;
		start = total_ability(i);
		link = total_ability(num - i - 1);
		if (abs(start - link) == 0) return 0; 
		if (abs(start - link) < min) min = abs(start - link);
		//printf("start : %d link : %d min : %d\n", start, link, min);
	}
	return min;
}

int main(void)
{
	input();
	team_combi(0, 0);
	//printf("%d\n", num);
	int ans = get_min();
	printf("%d", ans);
	return 0;
}

솔직히 이 문제는 보자마자 "조합써야하는구나"를 떠올렸지만, 아직 재귀가 익숙치 않아서 team_combi 함수는 구글링 결과를 변형해서 썼다.. ㅋㅋㅋ 아 파이썬이었으면 itertools에 combination 라이브러리로 한방인데.. 젠장할 

 

조합 경우의 수 구하는것이 핵심이었던 것 같고, 다른 함수들은 문제에서 요구하는대로 구현해주면 된다. 

아, 설명에 앞서 한 가지 주의할 점은 조합의 경우의 수를 담을 combi 배열을 정말정말 크게 잡아주어야 한다는 것이다. 참고로 타임아웃이나 14%에서 FAIL 받는 분은 아래 예시를 넣어보기를 바란다. 배열을 너무 작게 잡으면 경우의 수를 다 담지 못하는 불상사가 벌어진다.. 

 

//input
20
0 5 4 5 4 5 4 5 0 5 4 5 4 5 4 5 4 5 4 5
4 0 5 1 2 3 4 5 4 0 5 1 2 3 4 5 2 3 4 5
9 8 0 1 2 3 0 2 9 8 0 1 2 3 1 2 2 3 1 2
9 9 9 0 9 9 9 0 9 9 9 0 9 9 9 9 9 9 9 9
1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1
8 7 6 5 4 0 3 2 8 0 6 5 4 0 3 2 0 1 1 1
9 1 9 1 9 1 0 9 9 1 0 1 9 1 0 9 9 1 0 9
6 5 4 3 2 1 9 0 6 5 4 0 2 1 9 0 2 1 9 0
0 5 4 5 4 5 4 5 0 5 4 5 0 5 4 5 4 5 4 5
4 0 5 1 2 3 4 5 4 0 5 1 2 0 4 5 2 3 4 5
9 8 0 1 2 3 1 2 9 8 0 1 2 3 0 2 2 3 4 5
9 9 9 0 9 9 9 9 9 9 9 0 9 9 9 0 9 9 9 9
1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1
8 7 6 5 4 0 3 2 8 7 6 5 4 0 3 2 4 0 3 2
9 1 9 1 9 1 0 9 9 1 9 1 9 1 0 9 9 1 0 9
6 5 4 3 2 1 9 0 6 5 4 3 2 1 9 0 2 1 9 0
0 5 4 5 4 5 4 5 0 5 4 5 4 5 4 5 4 5 4 5
4 0 5 1 2 3 4 5 4 0 5 1 2 3 4 5 2 3 4 5
9 8 0 1 2 3 0 2 9 8 0 1 2 3 1 2 2 3 1 2
0 5 4 5 4 5 4 5 0 5 4 5 4 5 4 5 4 5 4 5
4 0 5 1 2 3 4 5 4 0 5 1 2 3 4 5 2 3 4 5
9 8 0 1 2 3 0 2 9 8 0 1 2 3 1 2 2 3 1 2

//조합의 경우의 수 : 184756
//즉 combi 배열의 행의 개수가 184756 보다 커야한다.

//total_ability 함수

팀의 능력치를 구하는 함수이다. 만약 N = 6이고, start팀이 (1, 2, 3) 이라면 (1, 2) (1, 3) (2, 3)의 능력치를 모두 더해야하기 때문에 for 루프 2개로 구현해줬다. 또한 (2, 1) (3, 1) (3, 2)의 경우도 더해주어야 한다. 

 

 

//get_min 함수

각 팀의 능력치를 구하는 것은 total_ability 함수를 동일하게 사용했다. 다만 team_combi 함수를 돌렸을 때 다음과 같이

1 2 3	// i = 0
1 2 4
1 2 5
1 2 6
1 3 4
1 3 5
1 3 6
1 4 5
1 4 6
1 5 6
2 3 4
2 3 5
2 3 6
2 4 5
2 4 6
2 5 6
3 4 5
3 4 6
3 5 6
4 5 6	// num - 1 -i

결과가 나오기 때문에 짝을 맞추어 start팀은 total_ability(i), link팀은 total_ability(num - i - 1)로 파라미터를 넘겨주었다. 

두 팀의 능력치 차를 절댓값으로 감싸주고, 그 결과가 만약 0일 경우 최소이므로 곧바로 리턴해줬다. 0이 아니라면 min과 비교하여 작을 경우 값을 갱신해주었다. 

주의해야 할 점은 min값을 엄청 크게 잡아줘야 한다는 것인데, abs(start - link)의 최댓값이 잘 가늠이 안되어 그냥 0x7fffffff로 잡아주었다.