1035: 최소 이동거리

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

---

1. 문제

• 수업과 동아리 활동과 과제로 바쁜 한기대 생들은 조별모임을 좀더 효율적으로 하고 싶어 합니다.
  조별 모임을 하기 위해서는 조원이 모두가 모임 장소로 이동을 해야 하는데, 전체가 이동하는 이동 거리의 합을 최소로 하고 싶습니다.
  문제를 간단하게 하기 위해서 우리가 1차원 직선상에 있다고 가정을 해보죠. 만약 위치가
    1, 4, 10
  에 있다고 한다면, 1의 위치로 모이면 총 이동거리는 0 + 3 + 9 = 12 가 되며, 4의 위치로 모이면 3 + 0 + 6 = 9 가 됩니다. 10으로 모여도 9보다 크며 다른지점 (2, 3, 5, 6, 7, 8, 9) 로 모여도 9보다는 더 많은 거리를 이동해야 합니다.

 

---

2. 문제의 조건

• 1 <= N <= 100,000 (조원의 수)
• 0 <= pos <= 100,000,000 (조원의 위치)
• 오름차순으로 주어진다.

 

---

3. 문제 접근

• 시간 복잡도
  
  제한시간 1초에 N이 10만이니 약 O(N^1.6)에 해결해야한다고 생각했습니다.

 

• 아이디어
  
  

  0	1	2	pos	0->pos	1->pos	2->pos	이동거리
  1	4	9	1	0	3	8	11
  1	4	9	2	1	2	7	10
  1	4	9	3	2	1	6	9
  1	4	9	4	3	0	5	8
  1	4	9	5	4	1	4	9
  1	4	9	6	5	2	3	10
  1	4	9	7	6	3	2	11
  1	4	9	8	7	4	1	12
  1	4	9	9	8	5	0	13
  1	4	9	10	9	6	1	16

  여러 표를 그려보시면 파악하시겠습니다만, 모두가 이동할 수 있는 최소 이동거리는 항상 "중간"이 됩니다.
  ※ n이 짝수 일 경우도 그려보면 아시겠지만 [1, 2, 5, 6]의 경우  2, 5는 둘다 최소로 같은 값을 가지게됩니다.
  
  즉, O(N)의 시간 안에 해결 할 수 있는 문제입니다!

 

---

4. 풀이 방법

• 배열의 중간의 idx를 구해줍니다.
• 그 각각의 원소에서 배열 중간 값을 뺀 것 들의 총 합을 구해줍니다.
  ※ 1, 4, 9의 경우
  1 - 4 = -3
  4 - 4 = 0
  9 - 4 = 5
  음수가 표시되므로 abs 절대값을 사용하여 해결

 

---

5. 소스코드

• cjw-git.tistory.com/39

 

---

 

cjw.git@gmail.com