imported>Unknown at 05:23, 7 February 2021

2021-02-07T05:23:03Z

New page

[http://acm.uva.es/p/v100/10003.html 원문보기]
----
=== 이 문제는 ===
인기도:B(A,B,C), 성공률:보통(낮음,보통,높음), 레벨:2(1~4)

=== About [[CuttingSticks]] ===
나무막대를 여러 조각으로 잘라야 한다. 절단 분야에서 가장 뛰어난 것으로 알려진 ACM(Analog Cutting Machinery)이라는 회사에서는 자를막대의 길이에 따라 요금을 부과한다. 그리고 톱의 구조상 한 번에 하나씩만 자를 수 있다.

절단 순서에 따라 요금이 달라진다는 것은 그리 어렵지 않게 알 수 있다. 예를 들어 10미터짜리 막대를 한 쪽 끝으로부터 2, 4, 7미터 위치에서 자르는 경우를 생각해보자. 자를 수 있는 방법은 매우 다양하다. 처음에 2미터 위치에서 자르고 그 다음에 4미터 위치, 마지막으로 7미터 위치에서 자를 수도 있다. 이렇게 하면 요금은 10+8+6=24가 된다. 첫번째 막대는 10미터였고, 그 다음 막대는 8미터였고, 마지막 막대는 6미터였기 때문이다. 하지만 일단 4미터 지점에서 자르고 2미터 지점에서 자른 다음 마지막에 7미터 지점에서 자르면 요금이 10+4+6=20이 되므로, 앞에서 잘랐던 방법으로 하는 것보다 요금을 줄일 수 있다. 어떤 막대가 주어졌을 때, 최소 절단 요금을 구하는 프로그램을 만들어보자.

=== Input ===
여러 테스트 케이스가 입력된다. 각 테스트 케이스의 첫째 줄에는 자를 막대의 길이를 나타내는 양의 정수 l이 입력된다. l은 1,000 미만이라고 가정하자. 그 다음 줄에는 잘라야 할 횟수 n (n < 50)이 입력된다.
그 다음 줄에는 n개의 양의 정수 Ci ( 0 < Ci < l) 가 입력되는데, 이 숫자들은 막대를 잘라야 할 위치를 나타내며, 오름차순으로 입력된다.(같은 정수가 두 번 입력되는 일은 없다.)
l의 값으로 0이 입력되면 입력이 종료된 것을 의미한다.

=== output ===
각 막대를 자르는 데 드는 최소 비용을 아래 예에 나와있는 것과 같은 식으로 출력한다.

=== Sample Input ===
100
3
25 50 75
10
4
4 5 7 8
0
=== Sample Output ===
The minimum cutting is 200.
The minimum cutting is 22.

=== 풀이 ===
{| class="wikitable"
|-
| 작성자
| 사용언어
| 개발시간
| 코드
|-
| 문보창
| C++
| 2일
| [[CuttingSticks/문보창]]
|-
| 김상섭
| C++
| 3년
| [[CuttingSticks/김상섭]]
|-
| 하기웅
| C++
| 몇일
| [[CuttingSticks/하기웅]]
|}

=== 쓰레드 ===
----
[[문제분류]] / [[경시대회준비반]]

CuttingSticks - Revision history

imported>Unknown at 05:23, 7 February 2021