78.9곳의 물류센터를 모두 연결하는 도로를 개설하려고 한다. 필요한 도로의 최소 길이는? (단, 구간별 숫자는 km임)

① 13km

정답: X

9곳을 잇는 데는 구간 8개가 필요한데, 고리 없이 가장 짧은 8개를 골라도 17km라 13km로는 모자란다.

② 14km

정답: X

구간을 7개만 골라(1 + 1 + 1 + 2 + 3 + 3 + 3) 한 곳을 빠뜨리면 14km가 나온다 — 9곳이면 8개가 필요하다.

③ 15km

정답: X

15km로는 모든 물류센터에 닿지 못한다 — 고리 없이 8개 구간을 이은 최솟값은 17km다.

④ 16km

정답: X

16km가 되려면 3km 구간 하나를 2km 구간으로 바꿔야 하는데, 2km 이하 구간은 이미 모두 썼다.

⑤ 17km

정답: O

짧은 구간부터 고리 없이 잇는다: B-C 1·C-E 1·H-I 1·A-D 2·A-B 3·C-H 3·D-F 3·G-I 3(D-E 3은 고리라 뺀다) → 1+1+1+2+3+3+3+3 = 17km.