고장에 대비한 기관차 운행 timer 1s memory 64MB

잘 알다시피 기차는 맨 앞에 있는 기관차 1대가 손님들이 탄 객차 여러 칸을 끌고 다닌다. 요즘 운행되는 기관차들은 오랜 시간 운행을 해왔고, 또 낡아서 철도청에서는 갑작스런 기관차 고장에 대한 대책 회의를 했다. 회의의 결론은 새로운 기관차를 새로 사는 것은 돈이 많이 들기 때문에 값이 싼 소형 기관차를 각 역마다 3개씩 예비로 두는 것이다. 이 소형기관차는 값이 싼 반면에 원래의 기관차보다 적은 수의 객차를 끌 수밖에 없다. 하지만 소형 기관차 3대 만으로는 원래 기관차가 끌 던 수만큼의 객차를 모두 끌 수 없다는 문제점이 제기 되었다. 이미 정책을 시행해 버렸고 위와 같은 문제점이 발생했기 때문에 소형 기관차들이 어떤 객차를 끌고 가는 것이 좋을까 하는 문제를 놓고 다음과 같이 결론이 내려졌다.

첫째, 소형 기관차가 최대로 끌 수 있는 객차의 수를 미리 정해 놓고, 그 보다 많은 수의 객차를 절대로 끌게 하지 않는다. 소형 기관차가 최대로 끌 수 있는 객차의 수는 서로 같다. 둘째, 소형 기관차를 운행하게 될 때는 최대한 많은 손님을 목적지까지 운송하도록 한다. 각 객차에 타고 있는 손님의 수는 미리 알고 있으며, 다른 객차로 손님들은 이동하지 않는다고 가정한다. 셋째, 각 소형 기관차는 연속적으로 이어진 객차를 끌게 한다. 객차의 번호는 편의상 기관차 바로 뒤의 객차를 시작으로 1번부터 번호를 부여한다.

예를 들면 기관차가 끌고 가던 객차가 7칸이고, 소형 기관차 1대가 최대로 끌 수 있는 객차의 수는 2칸이라고 하자. 그리고 1번부터 7번까지 각 객차에 타고 있는 손님의 수가 아래 표와 같다고 하자. 괄호 속에 있는 숫자는 객차 번호를 나타낸다.

위의 규칙을 따르면 소형 기관차 3대는 각각 1-2번, 3-4번, 그리고 6-7번 객차를 끌고 가면 손님 240명을 운송할 수 있고, 이보다 많은 수의 손님은 운송할 수 없다. 기관차가 끌고 가던 객차의 수와 각 객차에 타고 있던 손님의 수, 그리고 소형 기관차가 최대로 끌 수 있는 객차의 수가 주어질 때, 소형 기관차 3대를 이용하여 최대로 운송할 수 있는 손님의 수를 구하는 프로그램을 작성하시오.