BOJ 1349

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

 

코드

http://boj.kr/01722eeb80874eb5a548de9a33448799

 

난이도 : P2

 

Elapse Time : 50min

 

문제를 보고 든 생각은 2개였다. 최종적으로 모든 도시 쌍이 연결되어 있어야 하고 그 비용을 최소화하는 문제이기 때문에 최소 스패닝 트리와 연관이 있을 것 같다는 것과 $N$이 많이 작아 모든 도시 쌍을 다 살펴보는 것이 가능하다는 것이었다. 이 문제에서는 도로의 추가가 없더라도 들어갈 수밖에 없는 고정 비용이 존재한다. 각 도시별로 추가적인 집을 짓는 데 $ \frac{(A_i-B_i)(A_i+B_i-1)C_i}{2}$의 비용이 들고, 연결된 $(i,j)$의 쌍에 대해 $(A_i-B_i)(A_j-B_j)\mathrm{min}(C_i,C_j)+B_iC_j(A_j-B_j)+B_jC_i(A_i-B_i)$의 비용이 든다. 우선 이 비용을 다 더하고 모든 쌍이 연결되어 있기 위해서 추가적으로 드는 비용을 최소화 하는 방법에 대해 생각했다. 여기서 이미 연결되어 있는 $(i,j)$에 대해서는 연결해도 추가 비용이 발생할 뿐이므로 연결할 필요가 없다. 연결되어 있지 않은 $(i,j)$에 대해서는 연결할 때 $(A_i-B_i)(A_j-B_j)\mathrm{min}(C_i,C_j)+B_iC_j(A_j-B_j)+B_jC_i(A_i-B_i)+(B_i+B_j)R$ 의 비용이 추가적으로 든다. $(i,j)$에 대해 연결하는 데 드는 추가비용이 고정되어 있으므로 모든 $(i,j)$쌍을 비용 순으로 정렬해 두고 최소 스패닝 트리를 만들듯이 모든 쌍이 연결되어 있도록 하는데 드는 추가비용의 최솟값을 계산했다. 여기서 이 풀이가 정당화되기 위해서는 최소 비용을 소모하기 위해 건설하는 집의 순서가 일관적이어야 한다는 것인데, 이 순서는 대해 $C_i$가 증가하는 순서이므로 일관적이다.