글 읽기 - 시간초과

davidbecham 3년 전 0

시간초과가 왜 생기는지 모르겠어요 ㅠㅠ

#include <iostream>
#include <algorithm>

using namespace std;

struct PIZZA {
	int y, x;
};

struct HOUSE {
	int y, x;
};

int n, m;
int map[50][50];
PIZZA pizza[50];
int pizza_size = 0;
HOUSE house[50];
int house_size = 0;
int answer = 2147000000;
int check[50];

int distCheck() {
	int ret = 0;
	for (int i = 0; i < house_size; i++) {
		int minCheck = 2147000000;
		for (int j = 0; j < m; j++) {
			int c = abs(house[i].x - pizza[check[j]].x) + abs(house[i].y - pizza[check[j]].y);
			minCheck = min(minCheck, c);
		}
		ret += minCheck;
	}
	return ret;
}

void dfs(int cnt, int idx) {
	if (cnt == m) {
		int candi = distCheck();
		answer = min(answer, candi);
		return;
	}
	for (int i = idx; i < pizza_size; i++) {
		check[cnt] = i;
		dfs(cnt + 1, i + 1);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			cin >> map[y][x];
			if (map[y][x] == 2) {
				pizza[pizza_size].y = y; pizza[pizza_size++].x = x;
			}
			if (map[y][x] == 1) {
				house[house_size].y = y; house[house_size++].x = x;
			}
		}
	}
	dfs(0, 0);
	cout << answer << "\n";
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과

davidbecham 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말