[백준][삼성 SW 역량 테스트][Gold 5][C++] 15686 치킨 배달

문제

백준 삼성 SW 역량 테스트 기출 문제 - 15686 치킨 배달 (Gold 5)

15686번: 치킨 배달

 

---

문제 풀이

접근 방식

이 문제는 폐업시키지 않을 치킨집을 최대 M개 골랐을 때, 도시의 치킨 거리의 최솟값을 구하는 문제이다.

 

이 문제를 풀기 위해 필요한 정보는 집의 위치와 치킨집의 위치이다.

그래서 입력을 받을 때 map을 만들어 값을 저장하지 않고, 집의 위치와 치킨집의 위치만 저장해주었다.

 

그 후, next_permutation을 활용하여 치킨집을 M개 선택하였고,

이중 for문으로 치킨 거리의 최솟값을 구해주었다.

 

---

풀이 코드 - C++

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

using namespace std;

int N, M;
vector<pair<int,int>> house;
vector<pair<int,int>> chicken;


int main() {
	// 입력 받기
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int a;
			cin >> a;
			if (a == 1) {
				house.push_back({ i,j });
			}
			else if (a == 2) {
				chicken.push_back({ i,j });
			}
		}
	}

	// 치킨집 선정 & 최단 거리 구하기
	int chicken_len = chicken.size();
	int house_len = house.size();
	int MIN = 987654321;
	vector<int> idx(chicken_len);
	for (int i = 0; i < M; i++)
		idx[chicken_len - 1 - i] = 1;

	do {
		int sum = 0;
		for (int i = 0; i < house_len; i++)	{
			int MIN_distance = 987654321;
			for (int j = 0; j < chicken_len; j++) {
				if (idx[j]) {
					int distance = abs(house[i].first - chicken[j].first) + abs(house[i].second - chicken[j].second);
					if (MIN_distance > distance)
						MIN_distance = distance;
				}
			}
			sum += MIN_distance;
		}
		if (MIN > sum)
			MIN = sum;
	} while (next_permutation(idx.begin(), idx.end()));

	cout << MIN;
}

실행 결과

실행 결과 : 통과 (4ms)