R03461
Minimum Cost to Cut a Stick
골드 IV레이팅
의견: 0
설명
길이 \(L\)의 막대에 잘라야 하는 \(M\)개의 위치가 표시되어 있다. 한 번 자르는 비용은 그때 자르고 있는 막대 조각의 길이와 같다. 자르면 조각이 둘로 나뉘며, 자르는 순서는 자유롭게 정할 수 있다. \(M\)개의 컷을 모두 수행하는 최소 총 비용을 구하시오.
제약
입력 형식
첫 줄에 \(L\)과 \(M\)이 주어진다 (\(1 \le L \le 10^5\), \(0 \le M \le 40\), \(M \le L-1\)). 둘째 줄에 \(M\)개의 서로 다른 자르는 위치(\(0\)과 \(L\) 사이의 정수)가 주어진다. \(M = 0\)이면 빈 줄일 수 있다.
출력 형식
최소 총 자르기 비용을 출력한다.
예제 1
입력
7 4
1 3 4 5
출력
16
예제 2
입력
9 5
5 6 1 4 2
출력
22
예제 3
입력
10 0
출력
0
문제 정보
riseoj 작성
출처 RiseOJ Basics
태그
평가 및 의견
Minimum Cost to Cut a Stick
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Minimum Cost to Cut a Stick
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기