A시 소재 회사에 근무하는 갑은 B시에서 오후 3시에 개최되는 회의에 참석하고자 한다.
<표 1>과 <표 2>의 조건이 주어졌을 때, 오전 11시에 회사에서 출발하여 회의시간에 늦지 않게 도착하기 위한 방법 중 최저운임으로 갈 수 있는 방법과 최단시간에 도착할 수 있는 방법은?

<표 1> 교통수단별 소요시간과 운임(도시 내)

A시		교통수단	소요시간(분)	운임(원)	B시		교통수단	소요시간(분)	운임(원)
출발지	도착지				출발지	도착지
회사	공항	a	40	1,500	공항	회의장	a	35	1,500
		b	30	6,000			b	25	5,000
		c	30	1,500			c	35	2,000
	고속버스터미널	a	25	1,000	고속버스터미널		a	50	2,000
		b	15	3,000			b	30	6,000
		c	20	1,000			c	30	1,500
	역	a	30	1,000	역		a	30	1,000
		b	20	4,000			b	20	4,000
		c	15	1,000			c	35	2,000

<표 2> 교통수단별 소요시간과 운임(도시 간)

구간	교통수단	소요시간(분)	운임(원)	비고

| A시 → B시 | 비행기 | 90 | 60,000 | 탑승수속시간 35분 추가 소요 |
| | 고속버스 | 210 | 40,000 | |
| | 기차 | 140 | 50,000 | |

최저운임 도착방법　　　　　최단시간 도착방법

① 　c → 기차 → a　　　　　　c → 기차 → b

② 　a → 고속버스 → c　　　　c → 기차 → b

③ 　a → 비행기 → c　　　　　b → 비행기 → c

④ 　a → 기차 → a　　　　　　c → 비행기 → b

⑤ 　c → 고속버스 → c　　　　b → 비행기 → b