S전자 H캠퍼스에는 셔틀버스 한 대가 계속해서 사업장 사이를 원형으로 운행하고 있다.

캠퍼스 내에는 N개의 사업장이 있는데 사업장간 이동을 위해서는 셔틀버스가 매우 유용하게 활용되고 있다.

버스가 사업장마다 정차를 하게 되면 시간이 너무 오래 걸리기 때문에 정차하는 장소를 M개로 제한하려고 한다.

각 사업장마다 상주하는 인원을 기준으로 일정한 범위에 속한 그룹으로 나누어 각 그룹마다 한 곳의 위치를 정해서 정차를 하게 할 것이다.

그룹을 나누는 기준은 셔틀버스가 운행하는 코스를 기준으로 연속된 사업장의 상주인원 합의 차이가 최소가 되도록 하는 것이다.

예를 들어 아래와 같이 버스가 운행되는 코스에 5개의 사업장이 있고 각각 상주인원이 5, 20, 23, 15, 4명이라 할 때,

3개의 정류소를 만들고자 한다면 20명인 사업장에 1개, 23명인 사업장에 1개, 15 + 4 + 5명인 3개의 사업장에 한 개를 만들면

인원이 가장 많은 그룹은 24명이고 가장 적은 그룹은 20명이 되므로 그 차이가 4명이 된다.

이 방법이 최대인원과 최소인원의 차이가 최소인 경우가 된다.

만약 2개의 정류소만 만들어야 한다면 4 + 5 + 20 = 29, 23 + 15 = 38 이렇게 나누어서 차이는 9가 되고 이 방법이 최적이 된다.

사업장에 대한 정보를 입력받아 최대인원과 최소인원의 차이가 최소가 되도록 사업장을 나누어서 그 차를 출력하는 프로그램을 작성하시오.

정류소 만들기 timer 1s memory 256MB

정류소 만들기 1s 256MB