| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 99 | 18 | 13 | 26.531% |
BOJ 도시에는 1ドル$번부터 $N$번까지 번호가 붙은 $N$개의 토지가 일렬로 있고, 이 중 이미 분양된 토지가 $M$개 있다.
BOJ 도시의 시장인 청한이는 BOJ 도시를 개발하기 위해 아직 분양되지 않은 토지 중 $K$개를 분양하려고 한다. 단 도시와 멀면 토지의 수요가 줄어들기 때문에, 중심으로부터 멀어질수록 할인하여 분양하려고 한다. 구체적으로, 어떤 토지를 분양하는 시점에 이 토지의 왼쪽과 오른쪽에 있는 분양된 토지의 개수 차이를 $D$라고 할 때, 이 토지는 원래 가격에서 $D$만큼 할인하여 분양한다.
청한이는 BOJ 도시의 토지 중 $K$개를 골라 적절한 순서로 분양해서 최대한의 이익을 내고 싶다. 즉, 분양한 토지들이 할인된 양의 총합을 최소화해야 한다. 토지는 청한이가 정한 순서대로 하나씩 분양하며, 동시에 여러 개의 토지를 분양할 수 없다. 최적의 방법으로 토지를 분양했을 때, 할인된 양의 총합은 얼마인지 구하시오.
첫 번째 줄에 BOJ 도시의 토지의 개수 $N,ドル 이미 분양된 토지의 개수 $M,ドル 앞으로 분양할 토지의 개수 $K$가 주어진다.
두 번째 줄에 이미 분양된 토지의 번호를 나타내는 $M$개의 정수 $x_i$가 공백으로 구분되어 주어진다.
최적의 방법으로 토지를 분양했을 때, 분양한 토지들의 할인된 양의 총합을 출력한다.
6 2 2 1 3
3
1ドル$번 토지와 3ドル$번 토지가 이미 분양되어 있다. 6ドル$번 토지를 새롭게 분양하면, 왼쪽에 분양된 토지가 2ドル$개이고 오른쪽에 분양된 토지가 0ドル$개이므로 2ドル$만큼 할인해서 분양하게 된다. 그 이후 4ドル$번 토지를 새롭게 분양하면, 왼쪽에 분양된 토지가 2ドル$개이고 오른쪽에 분양된 토지가 1ドル$개이므로 1ドル$만큼 할인해서 분양하게 된다. 따라서 할인의 총합은 3ドル$이 된다. 이보다 더 적게 할인하면서 2ドル$개의 토지를 분양할 수 있는 방법은 없다.
Contest > BOJ User Contest > Good Bye, BOJ > Hello, BOJ 2023! E번