<정렬> BOJ 16210 나누어 생각하기

백준 16210 문제를 풀며 나누어 생각하는 것에 대해 이야기를 나누어보겠습니다.

1. 브루트포스
   특정 점에 대해 모든 점에 대한 거리를 구하고 그 중 최소값을 구한다.

• 복잡도
  각각의 점에 대해 모든 점을 돌아야하므로 $o(n^2)$인데 문제에서의 n제한은 50만이다. 따라서 총 250억으로 적합하지 않은 풀이입니다.

2. 나누어 생각하기

• 2-1. 문제에서 제시한 거리 계산식은 $|x_1-x_2|+|y_1-y_2|$입니다. 이 계산식을 $|x_1-x_2|$와 $|y_1-y_2|$로 나누어 생각해볼 수 있습니다.

• 2-2. 하지만 따로 구하더라도 모두 계산하게 되면 결국에는 1번 방법과 동일한 복잡도를 갖기 때문에 모두 하는 방법은 적합하지 않습니다. 그래서 정렬과 부분합 구하는 방법을 활용해 복잡도를 $o(n)$으로 줄여보겠습니다.

• 2-3. 정렬: x값을 저장하는 배열과 y값을 저장하는 배열을 만들어줍니다. (x값 y값이 원래 몇번째 은행의 값인지 알기 위해 index값도 배열에 같이 저장해둡니다)각 배열을 x값과 y값을 기준으로 정렬해줍니다.

• 2-4. 부분합: 배열의 특정 인덱스까지의의 합을 두 배열에 대해 구해줍니다. 참고로 배열에 대해 부분합을 구하는 것은 한번의 탐색으로 가능하므로 복잡도는 $o(n)$입니다.

  • 부분합이란 ? $S[i] = sum_{k=1}^{i}{a[k]}$

• 2-5. 2-3과 2-4를 통해 얻은 결과로 우리는 아래와 같이 x와 y각각에 대해 거리를 구할 수 있고 절대값과 동일한 효과를 얻습니다. 따라서 모든 i에 대해서 아래와 같이 복잡도 $o(n)$으로 x, y각각에 대한 거리를 구할 수 있습니다.
  

• 2-6. x와 y의 합이 가장 작은 index번호를 출력

이렇게 x와 y가 따로 놀아도 된다는 생각을 해보고 각각에 대한 거리를 구하여 복잡도를 줄일 수 있었습니다. 하지만 조금 지저분하다는 생각이 들어 기회되면 좀 더 깔끔한 방법을 생각해보겠습니다.