백준 14889 스타트와 링크 c++

해당 문제는 백트래킹 문제이다.

N명의 사람이 있고 N/2, N/2로 사람을 나눈 후에 능력치를 계산해주면 된다.

N/2, N/2로 팀을 백트래킹으로 나눠주었다.

그리고 cnt==N/2 가 되면 그 때 능력치를 계산해서 업데이트 해줬다.

정말 여러번 시간 초과가 났다.

 

#include <iostream>
#include <algorithm>
#include <cmath>

int N;
int arr[21][21];
int ans = 987654321;
int team[21];
using namespace std;

void dfs(int cnt, int start) {
	if (cnt == N / 2) {
		int total1 = 0, total2 = 0;
		for (int i = 0;i < N;i++) {
			if (team[i] == 1) {
				for (int j = 0;j < N;j++) {
					if (team[j] == 1) {
						total1 += arr[i][j];
					}
				}
			}
			else if (team[i] == 0) {
				for (int j = 0;j < N;j++) {
					if (team[j] == 0) {
						total2 += arr[i][j];
					}
				}
			}
		}
		ans = min(ans, abs(total1 - total2));
	}
	else {
		for (int i = start; i < N;i++) {
			team[i] = 1;
			dfs(cnt + 1, i + 1);
			team[i] = 0;
		}
	}
}

int main(void) {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	cin >> N;
	for (int i = 0;i < N;i++) {
		for (int j = 0;j < N;j++) {
			cin >> arr[i][j];
		}
	}
	dfs(0, 0);
	cout << ans << endl;
	return 0;
}

여러번 시간초과가 났는데 질문 게시판을 확인해보니 나와 비슷하게 푼 사람에게 cnt==N/2일 때 매번 능력치를 계산하는 부분이 시간초과의 원인이라고 지적했는데 N=20이 최대값이고 for문이 두개이니까 거기서 시간초과가 날 이유는 없다고 생각했다.

그래서 확인해보니 else 문에서 dfs(cnt+1, i+1)를 처음에 dfs(cnt+1, start+1) 로 주었었는데, i+1이 아니라 start+1이니 여러개의 중복된 콜이 있었다.

이 부분을 고치니 시간초과가 해결됐다.