본인 풀이

#include<bits/stdc++.h>
using namespace std;
int n, m, mn, r;
int a[54][54];
// 집, 치킨
vector<pair<int, int>> b;
vector<pair<int, int>> c;
vector<int> ret;

// 1. 치킨집 M개를 선택, 1 ~ M까지 for문
// 2. 치킨집 갯수마다 그에 맞는 치킨집 좌표를 조합
// 3. 각 좌표 조합으로부터 집까지의 치킨거리를 구함
// 4. 최솟값 저장 후 출력

// 완탐으로 가능한가? - 13C1 ~ 13C13까지 더하면? 2^13
// 5000 X 2N = 50000 - 가능
int solution(vector<int> v){
    int result = 0;

    // 각 집에서 모든 치킨거리를 계산할때 제일 작은 값을 가져야함
    for (auto it : b){
        int mnVal = 10e6;
        for (int idx : v){
            int xdist = abs(c[idx].first - it.first);
            int ydist = abs(c[idx].second - it.second);
            mnVal = min(mnVal, xdist + ydist);
        }
        result += mnVal;
    }

    return result;
}

// 치킨집 좌표 벡터의 인덱스를 가지고 접근
void combi(int start, vector<int> v){
    if(v.size() == r){
        ret.push_back(solution(v));
    }

    for(int i = start + 1; i < c.size(); i++){
        v.push_back(i);
        combi(i, v);
        v.pop_back();
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            cin >> a[i][j];
            if(a[i][j] == 1){
                b.push_back({i, j});
            }else if(a[i][j] == 2){
                c.push_back({i, j});
            }
        }
    }

    for (int i = 1; i <= m; i++){
        // 조합
        vector<int> v;
        r = i;
        combi(-1, v);
    }

    mn = ret[0];
    for (int val : ret){
        mn = min(val, mn);
    }
    cout << mn << "\n";

    return 0;
}

1. 로직 자체는 그렇게 어려운 문제는 아닌데 원복 대상을 결정하는게 너무 헷갈린다.
2. 치킨거리는 치킨집 중에 최대 M개를 선택하여 계산하게 된다.
3. 이때 실제 맵에 배치된 치킨집의 갯수가 M보다 클 수 있다. 즉 몇개의 치킨집은 어쩔 수 없이 폐업되어야 한다는 것이다.
4. 따라서 combi함수의 범위가 c.size()까지 순회를 하고, main함수에서는 치킨집의 갯수를 1~M까지 선택하도록 nC1, nC2... nCm의 경우의 수가 되는 것이다.

모범 답안

1. 조건을 정확히 이해하자. 완탐의 근거는 다름이아니라 2N이라는 조건때문이다.
2. 불필요한 시간복잡도가 추가되었다. 기존에 생각했던 시간복잡도는 최대 100이라고 가정하고, 치킨집 13개중 1 ~ 13개를 뽑는 조합수의 합 2^13이되며 총 80만정도 된다. 라고 생각했다. 하지만 문제에서는 치킨집 M개의 범위만 1~13이라고 한 것이지, 굳이 치킨집을 1개 ~ 13개까지 순회해가며 치킨거리를 계산할 필요는 없었다.
3. 따라서 13개 치킨집 중 6을 M으로 입력받고 이를 조합수의 r변수에 담아 로직을 계산하면 된다.

#include<bits/stdc++.h>
using namespace std;
int n, m, mn, r;
int a[54][54];
// 집, 치킨
vector<pair<int, int>> b;
vector<pair<int, int>> c;
vector<int> ret;

// 1. 치킨집 M개를 선택, 1 ~ M까지 for문
// 2. 치킨집 갯수마다 그에 맞는 치킨집 좌표를 조합
// 3. 각 좌표 조합으로부터 집까지의 치킨거리를 구함
// 4. 최솟값 저장 후 출력

// 완탐으로 가능한가? - 13C1 ~ 13C13까지 더하면? 2^13
// 5000 X 2N = 50000 - 가능
int solution(vector<int> v){
    int result = 0;

    // 각 집에서 모든 치킨거리를 계산할때 제일 작은 값을 가져야함
    for (auto it : b){
        int mnVal = 10e6;
        for (int idx : v){
            int xdist = abs(c[idx].first - it.first);
            int ydist = abs(c[idx].second - it.second);
            mnVal = min(mnVal, xdist + ydist);
        }
        result += mnVal;
    }

    return result;
}

// 치킨집 좌표 벡터의 인덱스를 가지고 접근
void combi(int start, vector<int> v){
    if(v.size() == r){
        ret.push_back(solution(v));
    }

    for(int i = start + 1; i < c.size(); i++){
        v.push_back(i);
        combi(i, v);
        v.pop_back();
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            cin >> a[i][j];
            if(a[i][j] == 1){
                b.push_back({i, j});
            }else if(a[i][j] == 2){
                c.push_back({i, j});
            }
        }
    }

    // 수정
    vector<int> v;
    r = m;
    combi(-1, v);

    mn = ret[0];
    for (int val : ret){
        mn = min(val, mn);
    }
    cout << mn << "\n";

    return 0;
}