저렴한 비행
시간 제한3초메모리 제한1024 MB
앞으로 비행이 몇 번일지 모른 채 항공기를 언제 살지 정하고, 총비용이 미리 아는 경우 최적값의 두 배를 넘지 않게 하는 문제입니다.
문제
당신은 BAPC 운영팀의 일원이며 항공 운항을 담당한다. 가끔 BAPC 심사위원들이 외딴 본부에서 BAPC가 현재 활동하는 현장인 암스테르담까지 이동해야 한다. 다행히 본부에서 암스테르담까지 가는 항공사가 있다. BAPC는 그 항공사와 계약을 맺어 항공편마다 같은 고정 요금을 낸다. 심사위원들이 이 노선을 자주 이용하면 비용이 쌓여 매우 커질 수 있다. 이를 피하려고 직접 항공기를 구입할 수 있다. 항공기를 소유하면 연료비 등 항공편마다 고정 요금이 드는 자체 항공기로 비행하거나, 여전히 항공사를 이용할 수 있다. 문제는 심사위원들이 무엇을 할지 전혀 알 수 없다는 것이다. 이들은 예측할 수 없고 항상 무작위로 매우 복잡한 일을 한다. 너무 무작위라서 미리 무엇을 할지 정할 수 없다. 따라서 비용 측면에서 최적인 결정을 미리 내리지 못하더라도 비행하면서 결정해야 한다. 그래도 지출을 지나치게 느슨하게 하고 싶지는 않다. 심사위원들이 몇 번 비행할지 미리 정확히 안다고 가정했을 때 지출하게 되는 금액의 최대 두 배까지만 쓰겠다고 스스로 제약을 정한다.