N개의 단어들이 있다. 이들 단어의 길이만 사용하므로 구체적으로 단어가 어떤 단어인지는 중요하지 않다. 이 단어들을 주어진 순서대로 k개의 줄에 출력하려고 한다. k < N 일 수 있으므로 한 줄에는 여러 개의 단어들이 들어갈 수 있다. 한 줄에 여러 개의 단어들이 들어간 경우 그 줄의 길이는 단어들의 길이의 합에 단어들을 구분하기 위해 추가한 빈칸의 개수가 될 것이다. 즉, 길이가 3, 4, 5인 단어들을 하나의 줄에 출력한다면 그 줄의 길이는 3+1+4+1+5 = 14이다.
하나의 가능한 출력 방법에 대해서 각 줄들의 길이가 비슷하면 좋은 출력으로 생각한다. 비슷한 정도의 구체적인 척도는 하나의 출력에 대해서 인접한 줄들의 길이의 차를 모두 구해서 더한 값을 최소화 하는 것이다. 이 척도를 출력의 ‘맞춤 값’이라고 부르자. 각 줄의 최대 길이 제한 M이 입력으로 주어진다.
주어진 입력에 대해 가능한 가장 작은 ‘맞춤 값’을 출력하는 프로그램을 작성하라.
입력 6 4 4 3 2 5 출력 3
출처:koi4u 2011 2 차모의고사 2 번