지헌이는 책꽂이를 만들려고 한다.

책꽂이의 설계도를 작성하고 보니 길이가 L1, L2, ..., LN(1≤Li≤50000)인 N(1≤N≤20000)개의 널빤지가 필요하다는 사실을 알았다.

지헌이는 목재상에서 필요한 크기(L1+L2+...+LN)의 널빤지를 구입했으나 필요한 크기로 자르기 위해서는 톱이 필요했다.

지헌이는 아무리 찾아 보아도 톱이 없다는 것을 알고 절망에 빠졌다.

이런 모습을 지켜보던 종현이는 지헌이에게 자신이 톱을 빌려줄테니 그 대가로 널빤지를 자를 때마다 그 널빤지의 길이만큼의 비용을 지불하라고 했다.

예들 들어 길이가 10인 널빤지를 둘로 나누게 되면 10의 비용을 지불하라는 것이다.

지헌이는 자신의 어려움에 처해 있다는 것을 이용해서 돈을 벌려고 하는 종헌이가 얄밉기는 했지만 달리 방법이 없어 그렇게 하기로 했다.

지헌이는 비용을 최소화하기 위해 자르는 위치와 순서를 잘 결정해야만 한다.

지헌이가 널빤지를 자르기 위해 필요한 최소한의 비용을 구하는 프로그램을 작성해 보자.

책꽂이 만들기 timer 1s memory 128MB

책꽂이 만들기 1s 128MB