막대자르기

UVA10003 막대 자르기

나무 막대를 여러 조각들로 잘라야만 한다.

가장 적당한 업체인 아날로그 벌목 공업사는 잘라야 될 막대의 전체 길이에 따라서 돈을 청구한다. 이들의 작업 절차는 한 시간에 한번만 자를 것을 요구한다.

자르는 순서를 달리하면 다른 조각들이 만들어질 수 있다.

예를 들어, 끝에서 2, 4, 7 미터에서 자를 수 있는 길이 10 미터의 막대기를 생각해 보자. 자르는 순서는 몇 가지가 있을 수 있다. 이럴 경우 처음 막대는 10 미터였으며, 자른 이후에는 8 미터에서 다음 4를 잘라야 하며, 마지막 한번 자르려면 6의 막대에서 자르므로, 10 + 8 + 6 = 24 의 돈을 막대 자르는 데 지출해야 한다. 또 다른 방법은 먼저 4에서 자르고, 다음은 2에서 자르면 4에서 2를 자르고, 마지막은 7에서 자르면 막대 길이 6짜리에서 자르므로 10 + 4 + 6 = 20 으로 더 싼 가격으로 막대를 자를 수 있다. 시장은 주어진 막대를 자르는 데 최소한의 비용이 드는 방법을 찾아내는 컴퓨터를 믿고 있다.

입력

입력은 몇가지 테스트 데이터로 구성된다. 각 테스트 데이터의 첫 번째 줄은 잘라야 할 막대의 길이를 표현하는 정수 L 이 입력된다. L은 1000보다 작은 값을 갖는다. 다음 줄에는 잘라야 할 막대 개수 n 이 입력된다. n 은 50보다 작은 양의 정수이다. 그 다음 줄은 잘라야 될 지점들이 Cj가 오름차순으로 n개 입력된다. Cj의 범위는 0 < Cj < L 이다.

테스트 데이터 첫 줄에 L 이 입력되면 입력 종료를 나타낸다.

출력

주어진 막대를 자르는 최소한의 비용을 계산하는 벌목 문제의 최적의 해답을 출력해야만 한다. 출력 형식은 아래 출력 예제를 참고하여라.

입력 예제

100

3

25 50 75

10

4

4 5 7 8

0

출력 예제

The minimum cutting is 200.

The minimum cutting is 22.

막대 자르기.cpp

막대자르기 테이블.xlsx

막대자르기 테이블2.xlsx