백준 15686 // 조합함수암기!

15686번: 치킨 배달 (acmicpc.net)

15686번: 치킨 배달

*로직

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;
}