치킨 배달(백준 15686)
치킨 배달 15686
1. 기본 설명
전형적인 브루트포스로 풀 수 있다. 이게 현재 solve.ac기준 골드 5라 책정되어있는데
아마 순열 조합 뽑기가 섞여있어 그런거 아닌가 싶다.
내가 푼 방법은 브루트포스라는 이름에 가장 걸맞는 방법으로, 현존하는 치킨집을 M개 맞춰 combination
으로 다 뽑은 다음, 모든 가능한 경우에 대해 min
값을 찾는다.
코드를 한번 봐 보자
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
long map[50][50] = { 0, };
vector<pair<long, long>> homeV;
vector<pair<long, long>> ChickV;
vector<vector<long>> V;
vector<long> curPath;
long N, M;
long distance(pair<long,long> home, pair<long,long> chick) {
return (long)(abs(chick.first - home.first) + abs(chick.second - home.second));
}
void Combination(vector<long> arr,vector<long> comb, long r, long index, long depth)
{
if (r == 0)
{
V.push_back(comb);
}
else if (depth == arr.size()) // depth == n // 계속 안뽑다가 r 개를 채우지 못한 경우는 이 곳에 걸려야 한다.
{
return;
}
else
{
// arr[depth] 를 뽑지 않은 경우
Combination(arr, comb, r, index, depth + 1);
// arr[depth] 를 뽑은 경우
comb.push_back(arr[depth]);
Combination(arr,comb, r - 1, index + 1, depth + 1);
}
}
long shortCut() {
long _count = 0;
long ret;
for (long i = 0; i < homeV.size(); i++) {
ret = 987654321;
for (long j = 0; j < ChickV.size(); j++) {
ret = min(ret, distance(homeV[i], ChickV[j]));
}
_count += ret;
}
return _count;
}
// 무시무시한 3중 for문... 그래도 N 50에 M 13이니 너무 쫄 필요는 없을듯하다.
// 50개의 집이 직접 13개의 점포를 확인해도 650밖에 안된다. 테스트 케이스가 13개중 4개를 뽑는다 해도 백만도 안된다.
long compShortCut(long testCase) {
long ret = 987654321;
long curMin;
for (long i = 0; i < testCase; i++) {
long _count = 0;
for (long j = 0; j < homeV.size(); j++) {
curMin = 987654321;
for (long k = 0; k < V[i].size(); k++) {
curMin = min(curMin, distance(homeV[j], ChickV[V[i].at(k)]));
}
_count += curMin;
}
ret = min(_count, ret);
}
return ret;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
for (long i = 0; i < N; i++) {
for (long j = 0; j < N; j++) {
cin >> map[i][j];
if (map[i][j] == 1) {
homeV.push_back(pair<long,long>(i,j));
}
else if (map[i][j] == 2) {
ChickV.push_back(pair<long, long>(i, j));
}
}
}
long ans =0;
if (M >= ChickV.size()) {//M과 현재 치킨점포수가 같으면 그냥 숏컷함수로 바로 찾는다. 이건 쉽다.
ans = shortCut();
cout << ans;
}
else {// 킹치만, 다를 경우 먼저 치킨점포수를 M의 개수로 뽑아서 shortcut을 돌려야 한다.
vector<long> combi;
vector<long> arr1;
for (long i = 0; i < ChickV.size(); i++) {
arr1.push_back(i);
}
// 가장 기본적인 조합 함수이다. 재귀 호출로 모든 조합을 찾는다.
Combination(arr1, combi, M, 0,0);
// 모든 조합에 대해 shortcut과 같은 함수를 돌려 최소 치킨거리를 찾고 그중에서 또 최소값을 찾는다.
long ans = compShortCut(V.size());
cout << ans;
}
return 0;
}
2. 작동 원리
- 자세한 내용은 주석을 참고하면 되겠다.
일단 현존하는 모든 조합을 찾는다. 거기에 최소가 되는 치킨집 거리를 3중 for
문을 돌려서 찾는다.
매우 간단하고 무식한 방법이지만 가장 직관적인 방법이라 생각된다.
3. 배운 점
- 이번에도 또 출력에서 실수해서 몇번 실패가 떴다. 항상 출력부분을 잘 생각하자
- 너무 어렵게 생각하지 말자. 물론 최적화가 필요한 문제이면 더욱 최적화를 해서 내야하지만 굳이 그렇게까지 하지 않아도 생각보다 컴퓨터는 빠르다.
- 직관적으로 짜고 나서 추후에 업그레이드를 하는 방식으로 천천히 생각하자. 처음부터 원대한 알고리즘을 떠올리기란 쉽지 않다.
Author And Source
이 문제에 관하여(치킨 배달(백준 15686)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@csm2652/치킨-배달백준-15686저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)