인프런 커뮤니티 질문&답변

강의 영상은 보지 않고 시간 재어서 풀었는데

왜 틀렸는지 잘 모르겠습니다... (정확하게는 시간초과가 나네요..)

이 문제는 풀만하다고 해서 잘 풀었던 것 같은데 

잘 모르겠습니다ㅜㅜ!! 

예제는 잘 나오고 개인적으로 테스트 케이스 몇개 돌려본 결과 

이상이 없는 것 같은데 고민을 해보고도 잘 되지 않아서 질문 올려봅니다.

#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
#define N 17

using namespace std;


int map[3][N];
bool visited[N];


int n;
int total = 0;
int level = 0;
int wtotal = 0;
int btotal = 0;
int ans = 0;
int mini = 10000;

void DFS(int total, int level) {

	if (level == n/2) {
		wtotal = total;
		for (int i = 1; i <= n; i++) {
			if (!visited[i]) {
				btotal += map[2][i];
			}
		}


		ans = abs(wtotal - btotal);
		/*printf("wtotal : %d \n\n", wtotal);
		printf("btotal : %d \n\n", btotal);
		printf("ans : %d\n\n", ans);*/
		if (mini > ans) {
			mini = ans;
		}
		btotal = 0;


	}

	else {
		for (int i = 1; i <= n; i++) {

			if (!visited[i]) {
				visited[i] = true;
				total += map[1][i];
				level++;
				//printf("current total : %d level : %d\n\n", total, level);
				DFS(total, level);
				visited[i] = false;
				level--;
				total -= map[1][i];
			}

		}
	}

	


}



int main() {


	cin >> n;

	for (int i = 1; i <= n; i++) {
		int s, t;
		cin >> s >> t;
		map[1][i] = s;
		map[2][i] = t;
	}

	

	DFS(total, level);


	printf("%d ", mini);



}

감사합니다!!