[백준 25380] 커다란 도시(2022 정보 올림피아드 예선 중2)

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

25380번: 커다란 도시

매년 최고 난이도를 갱신하는 정보 올림피아드 문제들을 보면서 오늘도 능지의 한계를 느끼는 나.
문제들이 하나같이 호락호락하지가 않은데 이 문제도 한 3일은 고민해서 푼 것 같다 ㅋㅋㅋ
근데 정보 올림피아드 문제들 공식 풀이가 있다는 사실을 어제 알아가지고 정해를 봤는데 내 방법이 더 깔끔하고 괜찮아 보였다.

시간이 획기적으로 빨라진다거나 그런건 아닌데 수학적으로 더 아름답고 구현도 편한 느낌?
태그 보니까 누적 합, 이분 탐색 등등 있던데 내 풀이는 이분 탐색 그런거 없고 정렬만 쓸 것이다.

그럼 지금부터 시작

부분 점수 항목을 보니까 이런 게 있었다.

1	14	M = 1.
2	11	모든 경찰은 두 도로가 교차하는 지점에만 배치된다.
3	20	1 ≤ N, M ≤ 20.
4	25	1 ≤ N, M ≤ 1 000.
5	30	추가 제약 조건 없음.

여기서 2번 서브태스크를 보고 일단 이 상황에서 풀리는 공식을 만들고 본 문제에 더 적용해볼 것이다.
모든 경찰은 두 도로가 교차하는 지점에만 배치된다는 것은 무엇을 의미할까?
경찰 두 명이 만나려고 할 때 방향이 맞게 길만 따라가면 그게 곧 최단거리가 됨을 의미한다.

일단 문제에서 $y$축에 평행한 도로 $a_1,a_2,...,a_n$ 이 있고,
x축에 평행한 도로 $b_1,b_2,...b_m$이 있다고 했다.

경찰들이 $k$ 명 있다고 했으니까 각 경찰을 $p_1,p_2,...,p_k$라고 한다면..
일단 이 경찰들이 이동하는 거리중에 x축으로 이동하는 거리도 있겠고 y축으로 이동하는 거리도 있을 것이다
근데 우리는 그걸 각각 따로 분리해서 생각할 것이다. 어차피 모든 쌍에 대한 경찰들의 이동 거리만 구하면 되니까 따로 더해도 별 상관은 없음

이 그림 보면 파란점이 주황점으로 갈 때 $y$축 타고 $4$ 이동했고 $x$축 타고 $7$ 이동해서 합계가 $11$인데 이걸 따로 분리해서 생각하자는 것이다.
일단 경찰들이 x축으로 이동한 거리만 계산해보자.

그럼 그 문제를 다음과 같이 바꿀 수 있다.
수직선 위에 경찰이 $k$명 있다.
$P_1,P_2,...,P_k$ 는 $p_1\sim p_k$의 x좌표를 정렬해서 다시 번호를 붙였다고 보면 된다.
$(P_1\le P_2\le ...\le P_{k-1}\le P_k)$
이때 $\sum _{i=1}^k(\sum _{j=i+1}^k|P_i-P_j|)$ 를 구하시오.

그럼 점들이 이렇게 있을텐데

일부만 예시를 들어 설명해 보자면, $P_{i+1}-P_i$가 총 몇 번 지나다니게 되는지 알아보면 된다.
예를 들어 $P_2$와 $P_3$ 사이의 거리는 $P_2$ 왼쪽에 점이 2개 있고, ($P_2$ 포함해서 2개)
$P_3$ 오른쪽에 3개 있기 때문에 총 $2\times 3=6$ 번 지나다니게 되는 셈이다.

$\sum _{i=1}^{k-1}(P_{i+1}-P_i)(n-i)i$

최종적으로 $O(nlogn)$시간에 정렬하고 모든 쌍들의 거리를 구하는데는 $O(n)$이라서 $O(nlogn)$이 걸렸다.

여기까진 정석 풀이랑 똑같아서 글의 핵심이 아니니깐..

아무튼 문제는 이제 교차점말고 다른 곳에 경찰이 서 있을 때이다
왜냐하면 최단 경로가 빙 돌아서 가야 하는 경우가 생기기 때문이다
근데 우리는 앞에서 교차점에 서 있을 때의 정답을 구할 수 있으니까
그걸 이미 더해놓고 남은 찌끄레기들만 더해 주면 된다.
근데 점 $P_i,P_j$가 있을 때 이 두 점 사이에 세로선이 하나라도 있으면 찌끄레기는 없다고 봐도 무방하다.

돌아서 갈 필요가 없기 때문이다. 따라서 중간에 세로선이 없는 점들의 집합만 어떻게 잘 해주면 되는데
점 2개만 있을 때 어떤 경로가 더 가까운지 확인해 보자면..

$d_i$를 $P_i$의 양쪽 세로선 중 더 가까운 거리라고 정의했을때,
$d_1$과 $d_2$를 비교해서 더 작은 쪽의 방향으로 가는게 더 가까운 거리이다.
근데 $d_1$은 결과적으로 2번 지나다니는 셈이 되니 2번 더해줘야 한다.

점 여러개 있는 경우로 확장해 보자.

각 $d_i$를 모두 구해서 정렬한 뒤에 $1$부터 $k$까지 다시 번호를 붙인다.

 

이때 정석 풀이에서는, 각 $d_i$에 대해 어떤 지점까지는 왼쪽으로 돌아가는 게 더 가까운 경로이고 어떤 지점부터는 오른쪽으로 돌아가는 게 더 가까운 경로이기 때문에 이 부분을 이진 탐색으로 찾아주었다.

 

하지만 나는 다른 방법으로 이를 구했다.

$d_1$입장에서는 자신을 이용해서 만든 경로가 4개 있다.(자신을 제외한 나머지 점 4개로 가는 경로들)

따라서 $d_1\times 4\times 2$를 더해준다.

$d_2$는 경로가 3개 있다.(자신과 $d_1$을 제외한 나머지 점 3개로 가는 경로들)
마찬가지로 $d_1\times 3\times 2$를 더해준다.

 

$k$로 일반화하면 다음과 같다.

$2\sum _{i=1}^k(k-i)d_i$

그리고 앞에서 말했듯이 이건 가로로 걸어간 길이만 구한건데 세로도 별거 없다.
걍 앞에서 한거랑 똑같이 하면 된다.