| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 (추가 시간 없음) | 512 MB | 170 | 59 | 37 | 37.374% |
Albert는 지하 연구소의 보안을 강화하기 위해 감시용 로봇을 사용해보려 한다. 지하 연구소는 $N$개의 방이 있고 좌측부터 우측까지 1번부터 $N$번까지 번호가 붙어 있는데, 아래 그림처럼 기다란 복도 형태이다 (이 경우 $N = 5$ 이다.)
$i$번째 방과 $i+1$번째 방 사이의 거리는 $d_i$ 이며 아래 그림의 경우 $d = [2, 3, 1, 4]$ 이다. 편의상 이 문제에서 두 방 $i, j$ 사이의 거리를 $D(i, j)$로 나타내자 -- 따라서 $i \lt j$일 때 $D(i, j) = \sum_{i \le k \lt j} d_k$ 이며 $D(i, i) = 0$이다.
가령 이 예제에서 $D(1, 4) = d_1+d_2+d_3 = 6$이고 $D(3, 4) = d_3 = 1$ 이다.
Albert는 총 $M$대의 감시용 로봇을 활용하고 싶은데 우선 $N$개의 방을 적절하게 $M$개의 연속한 구역으로 쪼갠 후 각 구역을 하나의 감시용 로봇이 24시간 감시하도록 하고 싶다. 각 구역은 1개 이상의 연속한 방으로 구성되며, 각 방은 반드시 하나의 구역에 속해야 한다. 이후 각 로봇은 자신이 담당한 구역에 속한 방들을 감시하는데, 이 때 필요한 에너지의 양은 해당 구역에 속한 서로 다른 방간의 거리 총합과 같다. 즉, 어떤 구역이 $i$번 방부터 $j$번 방까지 포함한다면 이 구역을 감시하기 위해 필요한 에너지의 양을 $S(i, j)$라 하면 $S(i, j) = \sum_{i \le k \le l \le j} D(k, l)$ 이 된다 - 이 정의에 따르면 $S(i, i) = 0$ 임에 유의하자 (이 경우 감시용 로봇은 $i$번째 방에 가만히 있을 수 있으므로 에너지를 거의 소비하지 않는다).
예를 들어 $M = 2$ 인 경우, 총 4가지 다른 방법으로 5개의 방을 2개의 구간으로 나눌 수 있다 - 곡선으로 표시된 거리는 두 방 사이의 거리인 $D(\cdot, \cdot)$ 값을 나타낸다.
로봇이 사용하는 배터리의 용량이 너무 크면 돈이 많이 들기 때문에 Albert는 각 로봇이 필요로 하는 에너지의 양이 최소가 되도록 하고 싶다 - 즉, $M$개의 구역이 필요로 하는 에너지의 최댓값을 최소화 하고 싶다. 위 예제의 경우 첫 번째 혹은 두 번째 방법으로 구역을 나누는 것이 최적이며, 정답은 10이다.
Albert를 도와 $N,ドル $M,ドル 그리고 $d$값이 주어졌을 때, $N$개의 방을 $M$개의 연속한 구역으로 나눌 때 각 구역이 필요로 하는 에너지의 최댓값을 최소로 만들면 이 값이 무엇인지 구해보자.
입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 $N$과 $M$이 공백으로 구분되어 주어진다. 둘째 줄에 $N-1$개의 정수가 공백으로 구분되어 주어지는데 이는 $d_1, d_2, \dots, d_{N-1}$ 값을 나타낸다.
각 테스트 케이스의 정답을 각 줄에 출력한다.
5 5 2 2 3 1 4 5 3 2 3 1 4 5 4 2 3 1 4 5 5 2 3 1 4 8 3 1 3 2 3 1 2 3
10 2 1 0 8
예제 1: 본문에서 다루었다.
예제 2: 이 경우 [1, 2], [3, 4], [5] 로 세 개의 구역으로 나눌 경우 각 구역이 요구하는 에너지는 2, 1, 0이 된다. 모든 구역이 요구하는 에너지가 2 미만이 되도록 하는 방법은 없다.
예제 3: 이 경우 [1], [2], [3, 4], [5]로 네 개의 구역으로 나눌 경우 각 구역이 요구하는 에너지는 0, 0, 1, 0이 된다.
예제 4: 각 로봇이 각 방을 감시하도록 [1], [2], [3], [4], [5] 로 나누면 된다.
예제 5: [1, 3], [4, 6], [7, 8]로 나누면 각 구역이 요구하는 에너지는 8, 8, 3이 된다.