c++ 백준_15686_"치킨 배달"

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

 

치킨 aka GOD

​

처음에는 문제 이해를 잘못했다.

​

'최대 M개를 open 해둔다'

라는 말이 1~M개 open 중 가장 작은 도시의 치킨 거리를 구하는 줄 알았다.

​

문제를 그렇게 많이 풀어보진 않았지만

느끼기에

이런 문제에서, 골드5정도에

약간은 지저분한 저런 조건이 있는게 이상했다.

​

문제 자체는 어렵지 않아

답을 구하고

다른 사람의 풀이를 보니

​

'최대 M개를 open 해둔다' 라는 말은

'가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개라는 사실을 알아내었다.'

이 문장과 '프랜차이즈'라는 점을 같이 이해했어야했다.

​

그래서 프랜차이즈로

최대 M개를 open해두는 방법이 최대 이익이다! 라고 못박았기 때문에

그냥 M개 open한 상태에서 최소의 치킨 거리를 구하면 되는 것이다.

 

글을 못읽노

​

그래서 다시 코드를 그에 맞게 수정하였다.

 

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

vector<bool> open(13,false);
int ans = 100000000;

void dfs(vector<vector<int>> dist, int num,int M,int chicken_num,int idx,vector<int> order) {

	if (num == M) {
		int distance = 0;
		for (int i = 0; i < dist.size(); i++) {
			int mini = 100000;
			
			for (int j = 0; j < order.size(); j++) {
				mini = min(mini, dist[i][order[j]]);
			}
			
			distance += mini;
		}

		if (distance != 0 && ans > distance) {
			ans = distance;
		}
		return;
	}
	

	for (int i = idx; i < chicken_num; i++) {
		open[i] = true;
		order.push_back(i);
		dfs(dist, num + 1, M, chicken_num, i + 1,order);
		order.pop_back();
		open[i] = false;
	}

}

int main(void) {

	int N, M;
	cin >> N >> M;

	int t;

	vector<pair<int, int>> house;
	vector<pair<int, int>> god;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> t;
			if (t == 1)
				house.push_back(make_pair(i, j));
			else if(t == 2)
				god.push_back(make_pair(i, j));
		}
	}

	vector<vector<int>> dist(house.size());

	for (int i = 0; i < house.size(); i++) {
		int x = house[i].first, y = house[i].second;
		for (int j = 0; j < god.size(); j++) {
			int a = god[j].first, b = god[j].second;
			int dt = abs(x - a) + abs(y - b);
			dist[i].push_back(dt);
		}
	}

	vector<int> order;

	dfs(dist, 0, M, god.size(), 0,order);

	cout << ans;

}