2014년 6월 4일 지방선거에서 인천시장에 출마한 유영현 후보는 세월호 참사와 같은 해양사고를 방지하기 위해 인천에서 가장 많은 배가 운항되는 덕적도까지 해저터널을 만들겠다는 공약을 내걸어 시장에 당선이 되었다. 하지만 육지에서 덕적도까지 한 번에 연결할 수 있는 해저터널은 수심이 너무 깊은 구간 때문에 불가능하다는 진단이 나왔다.

따라서 여러 섬들을 연결하는 해저터널을 건설하고 수심이 깊은 일부 구간은 다리를 놓아 연결하는 방법을 모색하게 되었다.

다행스럽게도 인천아시안게임을 유치하면서 중앙정부로부터 인천지역의 섬들을 연결하는 다리를 K개까지 건설하는 비용을 지원받기로 하였다.

섬 사이에는 조류나 수심 등의 영향 때문에 다리나 해양터널의 건설이 아예 불가능한 곳도 많다.

문제의 편의를 위해 육지도 한 개의 섬이라고 가정을 하자.

두 섬 사이에 해양터널을 건설하는데 드는 비용은 그 섬 사이의 최대수심에 따라 결정이 된다.

그렇다면 육지에서 덕적도까지 연결하기 위해 수심이 가장 깊은 K개의 구간은 정부의 지원으로 다리를 건설하기로 하고 나머지 구간에서 수심이 가장 깊은 구간을 찾아 해저터널을 건설하기 위한 예산을 편성하려고 한다. 예를 들어 육지를 1 덕적도를 4, K가 1이라 하고 1-2-3-4를 연결하려고 할 때, 각 구간의 최대 수심이 2, 10, 5라고 하면,

수심이 10인 2-3구간은 다리를 건설하고 해양터널을 건설하는 구간의 최대 수심은 3-4사이의 5가 된다.

이 때 수심이 가장 깊은 구간의 수심이 최소가 되도록 경로를 구성해야 예산을 절감할 수 있다.

해양터널 또는 다리의 건설이 가능한 섬과 섬 사이의 최대 수심이 주어질 때 해양터널을 건설할 구간 중 최대 수심이 최소가 되도록 경로를 구성하여 그 값을 출력하는 프로그램을 작성하라.

#2760 upload 164 done 42 how_to_reg 35

해저터널 timer 1s memory 128MB

#2760

해저터널 1s 128MB