-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
선생님, 제 코드 한번만 봐주실 수 있나요?
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);
}
감사합니다!!
답변을 작성해보세요.
0
김태원
지식공유자2021.03.23
안녕하세요^^
타임리밋이 나는 이유가 위에 코드는 순열방식로 짜서 그렇습니다.
N명 중에서 N/2명을 뽑는 조합방식으로 짜야 타임리밋을 피할 수 있습니다.
답변 1