공장 배치 비용을 가장 작게 만들기

자바스크립트 코딩테스트 문제로 convex-hull-trick 주제를 연습해보세요. 난이도는 hard이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

today hard convex-hull-trick 함수명: solution 제한 시간: 500ms

문제 설명

오름차순으로 정렬된 후보 위치 positions와 각 위치에 공장을 지을 때 드는 기본 비용 costs가 주어집니다.

반드시 0번 위치에 첫 공장을 짓고, 이후 더 큰 인덱스의 위치를 골라 마지막 위치 n - 1까지 이어야 합니다. 어떤 이전 공장 j에서 현재 공장 i로 바로 이어 붙일 때 추가 이동 비용은 (positions[i] - positions[j])²입니다.

i번 위치에 공장을 지어 도달하는 최소 비용은 다음과 같이 정의됩니다.

dp[0] = costs[0]
dp[i] = costs[i] + min(dp[j] + (positions[i] - positions[j])²)  (0 <= j < i)

마지막 위치 n - 1에 도달하는 최소 비용을 반환하는 solution 함수를 작성하세요.

제한사항

positions와 costs의 길이는 같습니다.
positions의 길이 n은 1 이상 100,000 이하입니다.
positions는 오름차순으로 정렬되어 있으며, 같은 값은 없습니다.
각 positions[i]는 -1,000,000 이상 1,000,000 이하의 정수입니다.
각 costs[i]는 0 이상 1,000,000 이하의 정수입니다.
첫 공장은 항상 0번 위치에 지어진 것으로 봅니다.
반환값은 n - 1번 위치까지 도달하는 최소 총비용입니다.

예시

입력: [0, 2, 5], [3, 4, 1] → 출력: 21
입력: [0, 1, 3, 6], [0, 10, 1, 2] → 출력: 21
입력: [7], [5] → 출력: 5

힌트

식 (x[i] - x[j])²을 전개해 보세요.
x[i]²와 costs[i]는 현재 i가 정해지면 고정값입니다.
이전 j가 만드는 값은 (-2 * x[j]) * x[i] + (dp[j] + x[j]²) 형태의 직선으로 볼 수 있습니다.

해설

점화식을 그대로 계산하면 각 i마다 모든 이전 j를 확인해야 하므로 O(n²)입니다. n이 최대 100,000이면 사용할 수 없습니다.

식을 전개하면 다음과 같습니다.

dp[i] = costs[i] + min(dp[j] + (x[i] - x[j])²)
      = costs[i] + x[i]² + min((-2x[j]) * x[i] + dp[j] + x[j]²)

즉, 이전 위치 j 하나는 다음 직선 하나를 만듭니다.

기울기 m = -2 * x[j]
절편 b = dp[j] + x[j]²
직선값 = m * x[i] + b

현재 위치 x[i]에서 지금까지 추가된 직선 중 최솟값을 빠르게 찾으면 dp[i]를 계산할 수 있습니다. 위치 값 범위가 정해져 있으므로 Li Chao Tree를 사용하면 직선 추가와 최소 질의를 각각 O(log C)에 처리할 수 있습니다. 여기서 C는 가능한 positions 값의 범위입니다.

풀이 흐름은 다음과 같습니다.

dp[0] = costs[0]으로 시작합니다.
0번 위치가 만드는 직선 m = -2 * positions[0], b = dp[0] + positions[0]²을 자료구조에 넣습니다.
i = 1부터 차례대로 현재 positions[i]에서 최소 직선값을 질의합니다.
dp[i] = costs[i] + positions[i]² + 최소 직선값으로 계산합니다.
계산된 dp[i]로 새 직선을 만들어 추가합니다.
마지막 dp[n - 1]을 반환합니다.

위치가 음수여도 전개식은 그대로 성립합니다. 단, 비용 합은 커질 수 있으므로 JavaScript에서는 일반 Number 범위 안에서 계산하되, 중간값을 불필요하게 문자열로 바꾸지 않는 것이 좋습니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과