Algorithm/boj
백준 15686 // 조합함수암기!
Mini_96
2023. 5. 30. 14:37
15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸
www.acmicpc.net
*로직
1. 완탐? 13C6 * 50 * 13 <1억 -> ok
2.for(13Cm) for (home) for(치킨) min갱신,ret갱신
* 조합핵심코드
/*
* * 조합함수 암기
*
* 결과 : idx 조합결과
* chichenList[0] -> [0,1]
* chichenList[1] -> [0,2]
* chichenList[2] -> [1,2]
*/
void combi(int start, vector<int> v) {
if (v.size() == m) {
chickenList.push_back(v);
return;
}
for (int i = start + 1; i < chicken.size(); i++) {
v.push_back(i);
combi(i, v);
v.pop_back(); //원복
}
return;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int m, n,ret,result=987654321;
//char a[54][54];
int a[54][54];
vector<pair<int, int>> chicken,home;
vector<vector<int>> chickenList;
/*
* * 조합함수 암기
*
* 결과 : idx 조합결과
* chichenList[0] -> [0,1]
* chichenList[1] -> [0,2]
* chichenList[2] -> [1,2]
*/
void combi(int start, vector<int> v) {
if (v.size() == m) {
chickenList.push_back(v);
return;
}
for (int i = start + 1; i < chicken.size(); i++) {
v.push_back(i);
combi(i, v);
v.pop_back(); //원복
}
return;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL); cout.tie(NULL);
cin >> n >>m;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
cin >> a[i][j];
if (a[i][j] == 1) home.push_back({ i,j });
if (a[i][j] == 2) chicken.push_back({ i,j });
}
}
//입력끝
vector<int> v;
combi(-1, v);
for (vector<int> chList : chickenList)
{
int ret = 0;
for (pair<int, int> p : home)
{
int _min = 987654321;
for (int ch : chList)
{
int temp= abs(chicken[ch].first - p.first)
+ abs(chicken[ch].second - p.second);
_min = min(_min, temp);
}
ret += _min;
}
result = min(result, ret);
}
cout << result;
return 0;
}