SWEA 4012번: [모의 SW 역량테스트] 요리사

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH

SW Expert Academy

 

쉬운 문제이당

해당 그림같은 식재료의 조합이 있을 때, 이를 두 진영으로 나누어 시너지를 더한 값의 차가 최소가 되는 경우를 찾는 문제이다

 

그래서 bool 배열을 사용해서 0은 A음식, 1은 B음식 진영으로 나누고

dfs를 사용해서 해당 depth의 식재료를 0과 1의 경우의 수로 재귀 호출했다

(N이 16이하의 작은 수이기 때문에 가능하다)

 

진영 나누기를 완료했을 때, 각각 진영의 시너지를 전부 더해주면 완료

#include <cstdio>
int n,s[17][17],ans,tc,index[17];
void func(int dep) {
	if (dep == n) {
		int a = 0, b = 0,sub;
		for (int i = 0; i < n; i++) {	//식재료 A 시너지 확인
			int cur = index[i];
			for (int j = 0; j < n; j++) {
				if (cur != index[j]||i==j)continue;

				if (cur)a += s[i][j];
				else b += s[i][j];
			}
		}

		if (a > b)sub = a - b;
		else sub=b - a;

		if (sub < ans)ans = sub;

		return;
	}

	func(dep + 1);
	index[dep] = 1;
	func(dep + 1);
	index[dep] = 0;
}
int main() {
	scanf("%d", &tc);
	for (int T = 1; T <= tc; T++) {
		scanf("%d", &n); ans = 987654321;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				scanf("%d", &s[i][j]);

		func(0);

		printf("#%d %d\n", T, ans);
	}
	return 0;
}

확실히 옛날 문제라 그런지 테스트 케이스를 10개나 줘서 테케만 맞히면 통과한다 ㅠ

요즘은 빡빡해져서 테스트 케이스 생성 능력이랑, 문제 정의를 빡시게 해줘야 한다