[백준 C++] 15686 치킨 배달

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

15686번: 치킨 배달

 

 

우선, "최대 M개"라는 워딩이 매우 신경쓰인다. 무조건 M개만 남기고 없애는 게 아니라 막,, M-3개를 남기는 게 더 효율적일 수 도 있나?라는 생각을 했음 → 그럴리 없다. 무조건 M개여야 치킨거리가 가장 작다!!

 

우선 정답 코드는 바로 아래 코드이다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll n, m, tmp;
vector<pair<ll, ll>> chick, home;
ll a, b;
ll result = 2147483647;
vector<ll> mark;

ll dis(pair<ll,ll> a, pair<ll,ll> b) {
	return abs(a.first - b.first) + abs(a.second - b.second);
}

ll cal_chi() {
	ll res = 0;
	a = chick.size();
	b = home.size();
	for (ll i = 0; i < b; i++) {
		ll tmp1 = 10000;
		for (auto j:mark) {
			tmp1 = min(dis(chick[j], home[i]), tmp1);
		}
		res += tmp1;
	}

	return res;
}

void select(ll idx) {

	a = chick.size();
	b = home.size();

	if (mark.size() == m) {  //최대 개수인 m개를 남기는 게 제일 효율적
		result = min(result, cal_chi());
		return;
	}
	else {
		for (ll i = idx; i < a; i++) {
			mark.push_back(i);
			select(i+1);
			mark.pop_back();
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;


	//집, 치킨집 입력 받음
	for (ll i = 0; i < n; i++) {
		for (ll j = 0; j < n; j++) {
			cin >> tmp;
			if (tmp == 1) {
				home.push_back({ i,j });
			}
			else if (tmp == 2) {
				chick.push_back({ i,j });
			}
		}
	}

	select(0);

	cout << result;
}

 

뭐 간단하게 설명해보자면..

우선 dis함수는 pair, { x좌표, y좌표 } 를 인자로 주면 거리를 반환해주는 함수이다.

그 다음 cal_chi함수는 치킨 거리를 계산하는 함수이다. mark에는 내가 남길 (폐업시키지 않을) 치킨집의 idx를 저장해둘 것이다. 따라서 각 집에서 가장 가까운 치킨집과의 거리를 구해서 더하면 그게 치킨거리가 될 것.

main 함수를 보면 우선 치킨집 위치와 집 위치를 입력받을 것이다. {x,y}꼴로 pair을 이용해, vector형태로 저장해둔다.

그 후 select함수를 실행하는데 위에서 언급했다시피 mark에는 내가 선택할 치킨집의 idx를 저장할 것이다. 나는 M개의 치킨집을 남길 것이기 떄문에 mark의 size가 M보다 작을 때는 계속 mark에 추가해야한다. 재귀적으로 구현했고, i를 push하고 select를 호출. mark에 중복 idx가 들어가면 안되므로 select의 인자에 idx를 넣어 그보다 더 큰 i를 push할 수밖에 ㅇㅄ게 함.