백준 15661 링크와 스타트 (c++) : 피너클

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

 

그냥 전부 만들어 보면 되는 문제였다.

 

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

전부 입력받아준다. 이때 0부터가 아닌 1부터 입력을 받아줬다.

vector<int> start, link;

start팀과 link팀을 벡터로 만들고 번호를 넣었다 뺐다 반복할 것이다.

int cal(int b) {
	int sum = 0;
	if (b == 0) {
		if (start.size() == 0) return 987654321;
		for (int i = 0; i < start.size(); i++) {
			for (int j = 0; j < start.size(); j++) {
				sum += s[start[i]][start[j]];
			}
		}
	}
	else {
		if (link.size() == 0) return 987654321;
		for (int i = 0; i < link.size(); i++) {
			for (int j = 0; j < link.size();j++) {
				sum += s[link[i]][link[j]];
			}
		}
	}
	return sum;
}

각 팀의 총 능력치를 구하는 함수다.

if (start.size() == 0) return 987654321;
for (int i = 0; i < start.size(); i++) {
	for (int j = 0; j < start.size(); j++) {
		sum += s[start[i]][start[j]];
	}
}

중요한건 어떻게 계산하냐는 건데 

일단 만약 팀의 크기가 0이면 팀의 크기는 무조건 1명 이상이어야 한다는 조건에 위반되는것이니 예외처리 해준다.

그후 start안에 있는 모든 번호들을 더해주면 된다. 

int solve(int num) {
	if (num == n+1) {
		return abs(cal(0) - cal(1));
	}

solve함수다. num은 현재 숫자를 의미한다.

num이 n보다 커지면 모든 숫자들이 팀 안에 들어갔다는 뜻이다.

팀 능력치를 계산해서 팀 능력치 차이를 리턴한다.

	start.push_back(num);
	int a = solve(num + 1);
	start.pop_back();

	link.push_back(num);
	int b = solve(num + 1);
	link.pop_back();

	return min(a, b);
}

그 후에는 각 팀에 num을 넣었다 뺐다 하면서 solve함수를 돌려준다.

마지막엔 각 팀에 들어갔을때 중 가장 차이가 적은걸 리턴해주면 된다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int s[21][21];

vector<int> start, link;

int cal(int b) {
	int sum = 0;
	if (b == 0) {
		if (start.size() == 0) return 987654321;
		for (int i = 0; i < start.size(); i++) {
			for (int j = 0; j < start.size(); j++) {
				sum += s[start[i]][start[j]];
			}
		}
	}
	else {
		if (link.size() == 0) return 987654321;
		for (int i = 0; i < link.size(); i++) {
			for (int j = 0; j < link.size();j++) {
				sum += s[link[i]][link[j]];
			}
		}
	}
	return sum;
}

int solve(int num) {
	if (num == n+1) {
		return abs(cal(0) - cal(1));
	}
	start.push_back(num);
	int a = solve(num + 1);
	start.pop_back();

	link.push_back(num);
	int b = solve(num + 1);
	link.pop_back();

	return min(a, b);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

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

	cout << solve(1) << endl;
}

전체 코드다.