1090 - 체커

문제 링크

---

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

문제 요약

---

\(N\)개의 점이 주어진다. 이 때 적어도 한개의 점이 한 점위에 있도록 하기위해 움직이는 최소 횟수 , 적어도 두 개의 점이 한 점위에 있도록 하기위해 움직이는 최소 횟수, ... 적어도 \(N\)개의 점이 한 점위에 있게 하기위해 움직이는 최소 횟수를 구하는 문제다.

문제 풀이

---

모든 점을 모으는 것이 아니라는 것이 이문제를 어렵게 만드는 요소 중 하나다. 하지만 모든 점을 모으는데 있어 최선의 선택은 \(x\)좌표들의 중앙값, \(y\)좌표들의 중앙값으로 모이는게 최선이라는 생각을 살짝 변형하면 쉽게 풀 수 있다.

(\(N\)개의 점을 모두 모으는데 왜 중앙값이 최선이냐에 대해서는 완벽하게 증명을 하진 못하겠다.)

그렇다면 임의의 점 \(K\)개를 모을 때를 생각해 보자. 이 때 점 \(K\)개를 모을 때 최선의 선택 지점은 어떻게 점을 고르던 간에 \(N\)개의 점들의 \(x\)좌표들 중 하나, \(y\)좌표들 중 하나가 될 것이다. 여기까지 생각을 했다면 거의 다 푼것과 마찬가지다.

우리는 우리가 모을 점 \(K\)개를 결정하는 것이 아니라, 모일 곳을 결정을 한 뒤 \(K\)개를 뽑아볼 것이다. 모일 곳이 결정이 됐다면 \(K\)개를 뽑는다는 것은 정말 쉬운 일이다. \(N\)개의 점들 중 모일 곳에서부터 맨하탄 거리가 가까운 \(K\)개만 뽑으면 되기 때문이다. 이러한 과정을 모일 곳이 될 수 있는 가능한 후보군에 대해서 모두 다 해본다면 임의의 점 \(K\)개를 한곳으로 모으는데 있어 드는 최소 비용을 찾을 수 있다.

우리가 점을 모일 곳으로 선택할 수 있는 좌표의 개수는 최대 \(N^2\)개가 존재를 하고 각각의 경우마다 정렬을 해서 계산을 해야 하므로 \(O(NlogN)\)의 시간이 소요된다. 최종적으로 \(O(N^3logN)\)의 시간으로 문제를 해결할 수 있다.

소스 코드

---

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

const int INF = 987654321;
int n;
vector<pair<int, int>> vp;
set<int> sx, sy;

int main() {
  scanf("%d", &n);
  for (int i = 0 ; i < n ; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    vp.push_back({u, v});
    sx.insert(u);
    sy.insert(v);
  }
  
  vector<int> ans(n, INF);
  vector<int> xCoor(sx.begin(), sx.end());
  vector<int> yCoor(sy.begin(), sy.end());
  for (int x : xCoor) {
    for (int y : yCoor) {
      vector<int> dist;
      for(const auto& p : vp) {
        dist.push_back(abs(x - p.first) + abs(y - p.second));
      }
      sort(dist.begin(), dist.end());
      
      int sum = 0;
      for (int k = 0 ; k < (int)dist.size() ; ++k) {
        sum += dist[k];
        ans[k] = min(ans[k], sum);
      }
    }
  }
  
  for (int val : ans) {
    printf("%d ", val);
  }
}