15686번-치킨배달

문제

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

15686번: 치킨 배달

---

접근방법

1) 접근 사고

문제를 요약하면 치킨집을 m개의 경우를 선택했을때 각 집마다의 치킨 거리가 최소가 되는 것들의 합을 구하는 문제였습니다.

저는 치킨이 가능한 경우의수 m개를 numArr에 넣어주고 m - chicken.size()의 개수만큼 0을 넣은뒤 next_premutaion을 통해 모든 경우의 수를 만든뒤 집과의 거리를 연산하였습니다.

 

2) 시간 복잡도

O(n ^ 2)

 

3) 배운 점

 

4) PS

---

정답 코드

#include<bits/stdc++.h>
 
using namespace std;
const int MAX = 51;
int n, m;
int board[MAX][MAX];
vector<pair<int,int>> chicken;
vector<pair<int,int>> house;
int minret = INT_MAX;
int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> board[i][j];
            if(board[i][j] == 1)
                house.push_back({i, j});
            else if(board[i][j] == 2)
                chicken.push_back({i,j});
        }
    }
 
    vector<int> numArr;
    for(int i = 0; i < m; i++)
        numArr.push_back(0);
    for(int i = 0; i < chicken.size() - m; i++)
        numArr.push_back(1);
 
    do{
        auto calculator = [&](int i , int j) -> int{
            return abs(house[i].first - chicken[j].first) + abs(house[i].second - chicken[j].second);
        };
 
        int ret = 0;
        for(int i = 0; i < house.size(); i++){
           int minValue = INT_MAX;
            for(int j = 0; j < chicken.size(); j++){
                if(numArr[j] != 0)
                    continue;
                minValue = min(minValue, calculator(i, j));
            }
            ret += minValue;
        }
        minret = min(minret, ret);
    }
    while(next_permutation(numArr.begin(), numArr.end()));
 
    cout << minret <<"\n";
}