2006학년도 대학수학능력시험 9월 모의평가 수리 영역 가형 이산수학 30번

어느 도시에 다음 그림과 같은 모양으로 $14$개의 다리가 놓여 있다. 모든 다리를 오직 한 번 지나서 출발점으로 다시 돌아오는 방법은 없다.

모든 다리를 오직 한 번 지나서 출발점으로 다시 돌아올 수 있도록 네 지역 A, B, C, D 중에서 필요한 두 지역을 잇는 다리를 추가로 몇 개 건설하려고 한다. 각 지역을 잇는 다리를 새로 건설하는 비용이 다음 표와 같을 때, 필요한 최소 비용은 $n$(억원)이다. $n$의 값을 구하시오. [4점]

(단위 : 억원)