선생님, 제 코드 한번만 봐주실 수 있나요?
197
작성한 질문수 72
강의 영상은 보지 않고 시간 재어서 풀었는데
왜 틀렸는지 잘 모르겠습니다... (정확하게는 시간초과가 나네요..)
이 문제는 풀만하다고 해서 잘 풀었던 것 같은데
잘 모르겠습니다ㅜㅜ!!
예제는 잘 나오고 개인적으로 테스트 케이스 몇개 돌려본 결과
이상이 없는 것 같은데 고민을 해보고도 잘 되지 않아서 질문 올려봅니다.
#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명을 뽑는 조합방식으로 짜야 타임리밋을 피할 수 있습니다.
조합을 구할때 algorithm 함수 next_permutation 사용 가능 여부
0
457
1
최악의 경우 연산 질문이 있습니다.
0
411
1
로컬 환경과 다르게 오답이라고 나와서 문의 드립니다.
0
302
1
6강 3번 정사각형 그리키 코드 질문 드립니다.
0
242
1
1-5 효율적인 공부 dy를 시간(N)으로 하는 풀이 질문
0
320
1
반복수와 시간초 계산을 어떻게 하나요??
0
333
1
왜 DP로 풀어야하는지 궁금합니다
0
242
1
선생님 안녕하세요. 다른 풀이에 대한 질문이 있습니다.
0
223
1
문제 해결방법에 대한 질문이 있습니다.
0
245
0
바둑대회 코딩 질문
0
270
1
6분 11초에서 dis [0][][]3차원 격자판이있는데요. 격자판안에 숫자는 문제에 없던데 어떻게 구해지는건가요?
0
200
0
실전모의고사 5회 1번 패턴찾기 질문있습니다.
0
220
1
전역변수관련 질문입니다.
0
255
1
5-1 패턴찾기 문제 질문드립니다.
0
218
1
오렌지 나무 문제 질문드립니다
0
310
1
코드 한번 봐주시면 감사하겠습니다!
0
175
1
코드 한번 봐주시면 감사하겠습니다!
0
234
1
코드 한번 봐주시면 감사하겠습니다!
0
198
1
시작점의 ch
0
204
1
vector에서 질문이 있습니다~!
0
235
1
그대로 따라했는데 시간 초과가 나왔습니다
0
161
1
2회 모의고사 4번 숲속의 기사 코드 질문이 있습니다.
0
288
1
질문있습니다.
0
209
1
이렇게 풀면 반례가 어떻게되나요?
0
245
1





