문제
창재는 요즘 잘 나가는 외식 사업가이다. 창재가 운영하는 회사는 출장 뷔페를 전문으로 하고 있는데 K개의 출장 팀을 운영하고 있다. 각 팀은 저마다 음식공급을 위한 설비를 한 세트씩 갖고 있다. 매주 창재의 회사는 다양한 곳으로부터 주문을 받는다. 대개의 경우 창재는 하나의 주문에 대하여 한 팀을 배정한다. 각 팀은 고객에게 음식과 설비를 제공하고 각 설비의 사용법을 설명해준다. 고객은 행사가 끝난 후에는 모든 설비를 창재의 회사에 반납한다.
이번 주에는 창재가 운영하는 팀보다 많은 주문이 들어왔다. 따라서 몇몇 팀은 하나 이상의 행사에 투입되어야 한다. 이러한 경우 회사는 행사가 끝난 고객이 설비를 반납할 때까지 기다릴 수가 없으므로 설비를 공급한 팀에서 설비를 회수하여 다른 행사장으로 이동한다.
회사는 설비를 이동하는 비용에 관심이 많아 회사와 행사장, 행사장과 행사장 사이의 이동비용을 잘 조사하여 갖고 있다. 회사는 이동 비용에 대한 정보들을 이용하여 현재 있는 팀으로 주문받은 행사를 모두 마치는 데 필요한 이동비용의 최소 합을 알고자 한다. 주문들은 행사가 열리는 시간의 오름차순으로 정렬되어 주어지며 행사장의 번호가 i < j 일 때 i번째 행사와 j번째 행사 사이에는 충분한 시간간격이 있어서 설비를 이동시키는데 문제가 없다.
입력
첫 행에 주문의 개수 N (1 ≤ N ≤ 100), 출장 팀의 개수 K (1 ≤ K ≤ 100) 이 입력된다.
이어서 N개의 행에 정보가 주어지는데, i번 행에는 n-i+1개의 Cij (0 ≤ Cij ≤ 150)가 입력된다.
Cij 가 의미하는 것은 i번 장소와 i+j번 장소 사이의 이동비용을 의미한다.
회사는 1번 장소에 있으며 주문 장소의 번호는 2번에서 N+1번이다.
출력
모든 행사를 마치는데 필요한 이동비용의 최소 합을 하나의 행에 출력한다.(출장 팀은 각 팀이 맡은 행사가 끝난 후에 설비를 갖고 회사로 돌아올 필요는 없다.)
예제 #1
3 2
40 30 40
50 10
50
80
예제 #2
3 2
10 10 10
20 21
21
40
출처
ACM ICPC 2015
로그인해야 코드를 작성할 수 있어요.