-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
시간초과가 나는 이유가 궁금합니다!
20.03.30 00:34 작성 조회수 100
0
아래와 같은 코드로 하니 하나 뺴고 시간초과가 되어서 궁금합니다.
강의랑 비슷한 코드인데 왜 제 코드는 시간초과일까요?!
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int N, M;
vector<pair<int, int> > pizza;
vector<pair<int, int> > people;
int ch[13];
int res = 987654321;
int cal(int x1, int y1, int x2, int y2) {
return abs(x1 - x2) + abs(y1 - y2);
}
void dfs(int index, int cnt) {
if (cnt == M) {
int min = 0;
for (int i = 0; i < people.size(); i++) {
int dis = 987654321;
for (int j = 0; j <M; j++) {
int x = cal(people[i].first, people[i].second, pizza[ch[j]].first, pizza[ch[j]].second);
if(dis > x) dis = x;
}
min += dis;
}
if (min < res) res = min;
return;
}
for (int i = index; i < pizza.size(); i++) {
ch[cnt] = i;
dfs(index + 1, cnt+1);
}
}
int main() {
scanf("%d %d", &N, &M);
for (int i = 1; i <=N; i++) {
for (int j = 1; j <= N; j++) {
int x;
scanf("%d", &x);
if (x == 1) people.push_back({ i,j });
else if (x == 2) pizza.push_back({ i,j });
}
}
dfs(0, 0);
printf("%d\n", res);
return 0;
}
답변을 작성해보세요.
0
답변 1