1041: 최소 이동거리 구하기 - 2차원

Link : judge.koreatech.ac.kr/problem.php?id=1041

---

1. 문제

• 수업과 동아리 활동과 과제로 바쁜 한기대 생들은 조별모임을 좀더 효율적으로 하고 싶어 합니다.
  조별 모임을 하기 위해서는 조원이 모두가 모임 장소로 이동을 해야 하는데, 전체가 이동하는 이동 거리의 합을 최소로 하고 싶습니다.  (1, 4), (8, 1), (4, 2)
• 에 있다고 한다면, (4, 2)의 위치로 모이면 총 이동 거리가 10으로 최소가 됩니다.
• 문제를 간단하게 하기 위해서 우리가 2차원 평면상에 있고 이동은 x축, y축으로만 이동할 수 있다고 제한을 둡니다. 만약 위치가

 

---

2. 문제의 조건

• 1 <= N <= 100,000
• 0 <= x, y <= 10,000

 

---

3. 문제 접근

• 시간 복잡도
  
  해당 문제는 N의 범위가 최대 100,000이니 O(N^1.6) 시간에 해결하면 됩니다.

 

• 아이디어
  
  1차원의 최소의 이동거리 문제는 정렬 후 가운데 있는 위치가 서로에게 가장 가까운 거리입니다.
  하지만 2차원인 지금은 x, y가 있으므로 x에대해 가까운 위치, y에 대해 가까운 위치를 각각 구해주면 해당 포인트가 가장 가까운 거리가됩니다. 그 후 각 pos 위치에서 가까운 위치에 대한 x, y 의 절대값을 모두 더해주면 결과값이 나오게 됩니다.
  
  즉, 정렬에 대한 시간 복잡도는 N log(N)이므로 해당 시간 안에 풀 수 있을 것이라고 생각하였습니다.

 

---

4. 풀이 방법

• x 축을 기준으로 중간 값을 찾아냅니다.
• y축을 기준으로 중간 값을 찾아냅니다.
  
  해당 과정은 홀수이면 딱 중간이 떨어지지만, 짝수 일 경우는 떨어지지 않으므로 중간값 총합 // 2 로 잡습니다.
• temp_x, temp_y 각 나온 (t_x, t_y)에 대해 모든 위치에 대한 절대값을 빼주며 이동거리를 더해줍니다.

 

---

5. 소스코드

• cjw-git.tistory.com/148

 

---

 

cjw.git@gmail.com