• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

선생님, 제 코드 한번만 봐주실 수 있나요?

21.03.22 17:47 작성 조회수 118

0

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

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

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

잘 모르겠습니다ㅜㅜ!! 

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

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

#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);



}




감사합니다!! 

답변 1

답변을 작성해보세요.

0

안녕하세요^^

타임리밋이 나는 이유가 위에 코드는 순열방식로 짜서 그렇습니다.

N명 중에서 N/2명을 뽑는 조합방식으로 짜야 타임리밋을 피할 수 있습니다.

celestial_님의 프로필

celestial_

질문자

2021.03.31

오 과연 조합 방식으로 복습 이후 풀어보니 ac 받았습니닼ㅋㅋㅋ 선생님 감사합니다!!