15686. 치킨 배달

 

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

15686번: 치킨 배달

 

 

Point

 

• 모든 치킨집(2)중에 n개를 고른 다음, 각각의 집과의 거리를 계산한다.
• 각각 집의 치킨 거리는 각 집과 치킨집과의 (x좌표차의 절댓값 + y좌표차의 절댓값)의 최솟값.
• 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.
• 도시의 치킨거리의 최솟값을 출력

 

Solution 

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n' 

using namespace std;
int n,m;
int ans = -1;
vector<vector<int>> area(51,vector<int>(51,0));
vector<pair<int,int>> chicken;
vector<pair<int,int>> home;


int main()
{
    FASTio;
    cin >> n >> m;
	
    
    // 1번
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin >> area[i][j];
            if(area[i][j]==2)
            {
                chicken.push_back(make_pair(i,j));
            }
            else if(area[i][j]==1)
            {
                home.push_back(make_pair(i,j));
            }
        }
    }
    
	// 2번
    vector<int> d(chicken.size());
    for(int i=0;i<m;i++)
    {
        d[i] = 1;
    }
    for(int i=m;i<chicken.size();i++)
    {
        d[i] = 0;
    }
    sort(d.begin(),d.end());
		
    // 3번
    do
    {
        int sum = 0;
        for(auto &p : home)
        {
            vector<int> dists;
            
            // 
            for(int i=0;i<chicken.size();i++)
            {
                if(d[i]==0) continue;
                
                // 선택한 치킨집에 대해서만 거리계산
                auto &s = chicken[i];
                int d1 = abs(p.first - s.first);
                int d2 = abs(p.second - s.second);
                int dist = d1+d2;

                // 계산한 거리 dists에 푸쉬
                dists.push_back(dist);
            }


            // 계산한 거리중 최소값을 sum에 더해줌 -> 도시의 치킨 거리
            sum += *min_element(dists.begin(),dists.end());
        }

        if(ans==-1 || sum<ans)
        {   ans = sum;
        }

    } while(next_permutation(d.begin(),d.end()));
    
	// 4번
    cout << ans;

    return 0;
}

 

 

1번. 영역배열을 입력받고 영역값이 1이면 home에 좌표값 push, 2이면 chicken에 좌표값 push

 

2번.  1) 모든 치킨집중에서 m개를 고르기 위해 d 배열 생성

 

3번.   1) 0~m-1에 1설정 m~chicken.size()에 0을 설정하고 원소가 1인 인덱스에 해당하는 값을 가져오면 됨

          2) 1)에 관해 next_permutation 실행 -> 조합이 된다

          3) 거리 계산 -> 각각 집에 대한 치킨거리의  최솟값 sum에 더해줌 -> sum의 최솟값 ans에 저장