[고등부] 2024 KOI 2차대회 대비 모의고사 (2주차)

아름다운 도시인 정올시에는 총 N개의 집이 있으며, 각 집은 일직선 상에 동일한 간격으로 배치되어 있다. 이 도시의 시장으로 새로 취임한 커터씨는 시민들의 편리한 이동을 위해 새로운 도로를 건설하려고 한다.

연속하는 l개의 집에 비용이 x인 도로를 건설하면, 연결된 집들에게 각각 x+1-l 만큼의 이동 편의성을 제공한다.

이때, 하나의 도로로 한 번에 연결되는 집의 개수 l은 x 이하의 정수로 도로를 건설할 때 직접 설정할 수 있으며, 도로마다 서로 다른 값으로 설정하는 것도 가능하다.

단, 예산의 한계로 인해 도로 하나의 최대 비용은 P이며, 교통 혼잡을 막기 위해 두 개 이상의 도로가 같은 집에 겹치지 않도록 도로를 건설해야 한다.

모든 시민들을 만족시키기 위해, 커터씨는 각 집에서 요구하는 이동 편의성을 모두 제공해주려 한다.

또한, 도시의 예산을 아끼기 위해 건설하는 도로의 비용의 합을 최소화하고자 한다.

커터씨를 위해 각 집에서 요구하는 이동 편의성을 제공하기 위한 도로 비용의 합의 최솟값을 구해주자.