글 읽기 - 시간초과의 원인이 궁금합니다.

rladudgns 6년 전 0

시간초과가 왜 나는지 모르겠습니다. ㅠㅠ 어디서 코드가 헛도는건지 이 방법이 느린 것인지 궁긍합니다. ㅠㅠㅠ

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int, int>> m_locate;	// 전체 건물 위치
vector<pair<int, int>> c_locate;	// M개 선택된 건물 위치
vector<pair<int, int>> p_locate;	// 사람 위치
int result = 9999999;
int N, M;

int sum(int i, int j) {
	int min_ = 9999999;
	for (int k = 0; k < M; k++) {
		min_ = min(min_, abs(i - c_locate[k].first) + abs(j - c_locate[k].second));
	}
	return min_;
}

void complete(int cnt) {
	if (M == cnt) {
		int sum_ = 0;
		for (int i = 0; i < p_locate.size(); i++) {
				sum_ += sum(p_locate[i].first, p_locate[i].second);
		}
		result = min(sum_, result);
		return;
	}

	for (int i = cnt; i < m_locate.size(); i++) {
		c_locate[cnt] = m_locate[i];
		complete(cnt+1);
	}

}

int main() {
	ios::sync_with_stdio(false);
	cin >> N >> M;

	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int input;
			cin >> input;
			if (input == 2)
				m_locate.push_back(make_pair(i, j));
			else if (input == 1)
				p_locate.push_back(make_pair(i, j));
		}
	}

	c_locate.resize(M);

	for (int i = 0; i < m_locate.size(); i++) {
		c_locate[0] = m_locate[i];
		complete(1);
	}
	cout << result << endl;
}

kdk8361 6년 전 2

음... 조합을 완성 한 후 조합이 어떻게 구성되어 있는지 검사하시면 왜 틀렸는지 나올겁니다.

조합하는 부분이 문제네요.

테케는

이걸 돌려보세요.

rladudgns 5년 전 0

감사합니다. 조합을 잘못만들었네요 ㅠㅠ

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

문제

문제

출처

ICPC

시간초과의 원인이 궁금합니다.

rladudgns 6년 전 0

kdk8361 6년 전 2

rladudgns 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말