Boj 15686) 치킨배달

문제

백준 15686

방법 1 (틀림)

설명

각 치킨 집마다 모든 가정집으로부터의 거리를 누적해서 더해줌.

• 그리고 정렬해서 가장 낮은 m 개를 선택해줌.

근데 반례가 생김

• 모든 가정집 옆집에 치킨집을 줌.
• 그리고 아무데나 치킨집을 하나 더 넣어줌.
• m 이 가정집 갯수 - 1 인 경우 무조건 추가로 넣은 치킨집을 빼야함.
• 하지만 이 알고리즘은 그것을 보장하지 않음.
• 실제 반례

방법 2

설명

직접 재귀로 조합을 구현함

이 방법 말고 BitMask 방법이랑 std::next_permutation 을 써봤는데 재귀가 젤 빨랐음.

• bitMask 의 경우 \({}_{N}C_{M}\) 에서 \(M\) 이 \(0\) 부터 \(N\) 까지의 값을 모두 더한 경우를 다 쓰니까 느린게 당연하긴 함.
• std::next_permutation 의 경우는 이걸 참고해서 해봤는데 bitMask 랑 비슷하게 나옴.

시간복잡도

O(\({}_{N}C_{M}\))

코드

struct House { int x, y;};
struct Shop : House
{
    void AddDist(int in_x, int in_y) { dist_list.push_back(abs(in_x - x) + abs(in_y - y)); }
    vector<int> dist_list;
};


int n, m;
House houses[101]; int n_house;
Shop shops[14];    int n_shop;

int ans = numeric_limits<int>::max();
int idx_map[14];
void Solve(int cur = -1, int n_select = 0)
{
    if (n_select == m)
    {
        int tmp_sum = 0;
        for (int i = 0; i < n_house; i++)
        {
            int tmp = numeric_limits<int>::max();
            for (int j = 0; j < m; j++)
                tmp = min(tmp, shops[idx_map[j]].dist_list[i]);
            tmp_sum += tmp;
        }
        ans = min(ans, tmp_sum);

        return;
    }
    
    for (int i = cur + 1; i < n_shop - (m - n_select - 1); i++)
        Solve(idx_map[n_select] = i, n_select + 1);
}


int main()
{
    cin >> n >> m;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            char c; cin >> c;
            switch (c)
            {
            case '1': houses[n_house++] = { j, i }; break;
            case '2': shops[n_shop++] = { j, i }; break;
            }
        }
    
    for (int i = 0; i < n_shop; i++)
        for (int j = 0; j < n_house; j++)
            shops[i].AddDist(houses[j].x, houses[j].y);
    
    Solve();
    
    cout << ans;
}