[백준 BOJ] 15686. 치킨 배달
10 Aug 2021난이도
Gold V
문제 풀이
간단하게 생각해보면, M개의 치킨집을 고르고 그 치킨집들에 대해 도시의 치킨거리를 구한다음, 도시의 치킨거리가 최소가 될때를 선택하면 해결된다. M개의 치킨집을 고르는 경우의 수는 최대 13개의 치킨집에서 M개를 고르는 것이므로 \(\small C(13, M)\)이다. 그 다음, 최대 2N개의 집에서 치킨 거리를 계산해야하니 \(\small O(2N) \cdot O(M) \cdot O(C(13, M)) = O(2NM \cdot C(13, M))\)이 된다. 최대값을 생각해보면 \(\small 10^{8}\)을 넘기지 않으니 1초 이내에 수행 가능하다. 따라서, 이 아이디어를 그대로 구현하면 답을 만들어낼 수 있다. 그대로 코드로 구현하면 아래와 같다.
void solve(int idx, vector<pair<int, int>>& chosenChicken, vector<pair<int, int>>& chicken, vector<pair<int, int>>& house, int& M) {
if(chosenChicken.size() == M) {
int chickenDist = 0;
for(auto& element : house) {
int hy = element.first;
int hx = element.second;
int minimum = abs(hx - chosenChicken[0].second) + abs(hy - chosenChicken[0].first);
for(auto& c : chosenChicken) {
int cy = c.first;
int cx = c.second;
minimum = min(minimum, abs(hx - cx) + abs(hy - cy));
}
chickenDist += minimum;
}
ret = min(ret, chickenDist);
return;
}
for(int i = idx; i < chicken.size(); ++i) {
chosenChicken.push_back(chicken[i]);
solve(i + 1, chosenChicken, chicken, house, M);
chosenChicken.pop_back();
}
}
먼저 함수에서 호출하는 파라미터들을 살펴보자
void solve(int idx, vector<pair<int, int>>& chosenChicken, vector<pair<int, int>>& chicken, vector<pair<int, int>>& house, int& M)
idx는 선택을 시작할 치킨집의 시작 인덱스를 말하는것이다. chosenChicken은 선택한 치킨집들이 모인 벡터이다. chicken, house, M은 각각 치킨집, 집, 선택할 치킨집의 수라는 정보를 담고 있도록 했다.
if(chosenChicken.size() == M)
이 조건은 기저조건으로, 고른 집들 개수가 M개이면 모두 선택한것이니 그 아래에서 치킨거리를 계산하도록 해놓았다.
for(int i = idx; i < chicken.size(); ++i) {
chosenChicken.push_back(chicken[i]);
solve(i + 1, chosenChicken, chicken, house, M);
chosenChicken.pop_back();
}
이 부분에서 치킨집을 고르게 된다. 먼저 idx부터 시작해 chosenChicken에 넣는다. 그 다음, i + 1번째 인덱스를 가르키게 하여 재귀함수를 호출하여 똑같은 과정을 하게 한다. 호출이 끝나면, chosenChicken에 담았던 치킨집을 제거한다. 그럼 for문이 i를 증가시키고 다음 치킨집을 넣고 재귀함수 호출하고 빼고 하는 과정을 계속 할 것이다. 이렇게 조합을 구현할 수 있는 것이다.
이렇게 치킨집조합을 구해 chosenChicken의 크기가 M이 되었으면 위의 if문에 걸려 들어가게 된다. 그럼 거기서 치킨거리를 계산해주면 끝이다. 거리를 계산하는 과정은 다음과 같다.
if(chosenChicken.size() == M) {
int chickenDist = 0;
for(auto& element : house) {
int hy = element.first;
int hx = element.second;
int minimum = abs(hx - chosenChicken[0].second) + abs(hy - chosenChicken[0].first);
for(auto& c : chosenChicken) {
int cy = c.first;
int cx = c.second;
minimum = min(minimum, abs(hx - cx) + abs(hy - cy));
}
chickenDist += minimum;
}
ret = min(ret, chickenDist);
return;
}
모든 집들에 대해 치킨거리를 구해 도시의 치킨거리에 더해준다. 그리고 전역변수로 선언된 ret에 최소값을 저장해주는 식이다. 그렇게 함수가 전부 호출이 끝나면, ret에는 답이 저장되어있으니 그걸 출력해주면 된다.
완전탐색으로 쉽게 해결할 수 있는 문제였다. 근데, 나는 이 문제 푸는데 곤혹을 겪었는데.. 그 이유는 solve(i + 1, …) 부분에 i대신 실수로 idx를 넣어서 시간복잡도가 매우 크게 되어버렸기 때문이다. 그래서 처음에는 TLE를 받았는데 저걸 찾고 제출하니 맞았다. 어이없는 실수이지만 찾기 어려운 실수라 조심할 필요가 있다. 저걸 idx로 넣게 되면 어떤일이 발생하게 되냐면, 쓸데없는 중복이 계속 발생하게 되어서 필요없는 연산을 무지성으로 반복하게 된다.