[c++][백준 15686][prev_permutaion] 치킨 배달 - 컴도리돌이

---

15686번: 치킨 배달

---

* 풀이 과정

1. 치킨 집 수에서 최대 M개를 선택해야 하기 때문에 본 문제는 순열 문제로 인식. prev_permutaion으로 문제를 해결하였다.

2. 초기 치킨집의 개수로 순열을 돌려서 시간 초과가 발생하였다. 

    ->해결 방안) combination이라는 치킨 집의 개수정도의 크기로 할당한 배열을 생성하여 인덱스가 0부터 m까지 true로 설정하였다.

       치킨집을 순열로 돌리지 않고 combination 배열을 순열로 돌려 해당 값이 false를 가지면 continue로 해서 중복된 값을 최대한 피         하려고 노력하였다.

---

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int n,m;

vector<pair<int,int>> city; /*도시의 좌표를 저장*/
vector<pair<int,int>> chichen; /*치킨 집의 좌표를 저장*/

void input()
{
    cin >> n >> m;
    for(int i=0,input; i<n; i++)
        for(int j=0; j<n; j++)
        {
            cin >> input;
            if(input == 1) city.push_back({i,j});
            if(input == 2) chichen.push_back({i,j});
        }
}
void solve()
{
    int answer = 987654321;
    
    vector<bool> combination(chichen.size()); /*순열로 돌릴 배열 생성(크기는 치킨 집의 크기 만큼)*/
    for(int i=0; i< m ; i++) combination[i] = true; /*m개의 true로 설정하여 후의 순열에서 중복된 값을 pass할 계획*/
    
    /*combination*/
    do
    {
        int sum = 0;
        for(int i=0; i<city.size(); i++)
        {
            int d = 987654321;
            for(int j=0; j<chichen.size(); j++)
            {
                if(!combination[j]) continue; /*중복 인덱스 pass*/
                int dist = abs(city[i].first - chichen[j].first) + abs(city[i].second - chichen[j].second);
                d = min(dist, d);
            }
            sum += d;
        }
        answer = min(answer,sum);
    }while(prev_permutation(combination.begin(),combination.end()));
    cout << answer;
}

int main(void)
{
    input();
    solve();
}

---