[c++ 알고리즘] 백준 15686: 치킨배달

 

문제를 보고 시간복잡도를 계산해봤다. 최대 13C7 * 700 이므로 투박하게 브루트 포스 알고리즘을 써도 될 것  같았다.

 

문제는 조합을 어떻게 구하냐는 것이었다.

 

조합 알고리즘을 구해 푸는 문제를 예전에 풀어봤지만 기억이 잘 나지 않는 관계로.. 조합 알고리즘만을 따로 공부한 뒤 접근했다.

 

조합 알고리즘을 구하는 상황이 여럿 있지만, 이 문제는 상황이 좋은 조합문제다. 1차원 배열 안에 들어 있는 Std::Pair 요소들을 m에 맞게 조합을 꾸려나가면 되기 때문이다.

 

그래서 단순하게 대표적인 조합 알고리즘 std::prev_permutation을 사용 할 수 있었다.

arr.assign(chi.size(), false);
	for (int i{ 0 }; i < m; i++) {
		arr[i] = true;
	}

	do {
		std::vector<std::pair<int, int>> tmp;
		for (int i{ 0 }; i < arr.size(); i++) {
			if (arr[i] == true) {
				tmp.push_back(chi[i]);
			}
		}
		ans = std::min(ans, search(tmp));
	} while (std::prev_permutation(arr.begin(), arr.end()));

 

Next_permutation 이 아닌 prev_ 를 사용하므로, 오름차순으로 true를 해야한다.

 

 

조합을 구현하는 것 말고는 크게 어려울 것 없는 문제였다. 다만, 시간복잡도를 제대로 파악해야 금방 풀 수 있을 것 같다.

 

#include <iostream>
#include <vector>
#include <algorithm>

int search(std::vector<std::pair<int,int>> ch);
int n, m;
std::vector<std::pair<int, int>> chi;
std::vector<std::pair<int, int>> city;
std::vector<bool> arr;

int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);

	int n, m;
	std::cin >> n >> m;


	int list[51][51] = {};

	for (int i{ 1 }; i <= n; i++) {
		for (int j{ 1 }; j <= n; j++) {
			std::cin >> list[i][j];
			if (list[i][j] == 1) {
				city.push_back(std::pair<int,int>(i,j));
			}
			else if (list[i][j] == 2) {
				chi.push_back(std::pair<int, int>(i, j));
			}
		}
	}

	int ans = 2147483647;
	arr.assign(chi.size(), false);
	for (int i{ 0 }; i < m; i++) {
		arr[i] = true;
	}

	do {
		std::vector<std::pair<int, int>> tmp;
		for (int i{ 0 }; i < arr.size(); i++) {
			if (arr[i] == true) {
				tmp.push_back(chi[i]);
			}
		}
		ans = std::min(ans, search(tmp));
	} while (std::prev_permutation(arr.begin(), arr.end()));

	std::cout << ans << "\n";
}

int search(std::vector<std::pair<int,int>> ch) {
	std::vector<int> minList(city.size(), 0);
	int cnt = 0;
	for (int i{ 0 }; i < city.size(); i++) {
		for (int j{ 0 }; j < ch.size(); j++) {
			int sec, fir;
			if (city[i].first - ch[j].first < 0) fir = -1 * (city[i].first - ch[j].first);
			else fir = city[i].first - ch[j].first;
			if (city[i].second - ch[j].second < 0) sec = -1 * (city[i].second - ch[j].second);
			else sec = city[i].second - ch[j].second;
			
			if (minList[i]==0) {
				minList[i] = fir + sec;
			}
			else {
				minList[i] = std::min(minList[i], fir + sec);
			}

		}
	}
	int ans = 0;
	for (int i{ 0 }; i < city.size(); i++) ans += minList[i];

	return ans;
}