문제

두 나라 A국과 B국은 항상 사이가 좋지 않은데, 국민들 간에 쌓인 감정을 털어버리기 위해 양국의 대표 선수들이 한 명씩 나와 친선 스포츠 경기를 하기로 했다. 채택된 종목은 철인 N종 경기이다. 철인 N종 경기의 코스는 여러 구간들로 구성되는데, 각 선수는 각 구간에서 정해진 종목을 이용해 결승점으로 이동해야 한다. 예를 들어, 어떤 철인 N종 경기의 코스는 수영 1500km, 마라톤 42.195km, 크로스컨트리 60km, 기어가기 1km 으로 구성될 수 있다.

당신은 국제 철인 N종 경기 협회장으로서, 이 경기에 사용될 종목들과 그 순서를 정하는 역할을 하게 되었다. 두 나라 국민 사이 감정의 앙금을 쌓이지 않게 하기 위해, 가능한 한 두 대표 선수가 비기도록 종목들을 고르고 싶다. 다행히, 당신은 협회장이기 때문에 두 선수가 각 종목에 걸릴 시간을 비교적 정확히 예상할 수 있다. 당신의 예상이 정확하다고 할 때, 두 선수가 비기도록 코스를 설계할 수 있을까? 또한, 비기는 코스 중 걸리는 시간이 가장 짧은 코스는 무엇일까?

이와 같이 5개의 종목이 있다고 하자. 그러면, 남산 스키타고 내려오기로 코스를 정하면 양국 선수가 비긴다는 것을 쉽게 알 수 있다. 그러나 그보다 더 좋은 방법이 있다. 63빌딩 계단 오르기 이후 2000m 깽깽이 뛰기를 두번 하도록 코스를 정하면 양국 선수 모두 37분으로 비기기 때문이다.

이와 같은 최적의 코스를 찾는 프로그램을 작성하라.

단, 한 종목을 두 번 이상 코스에 추가할 수도 있다.