배터리 셀 병합 강화

문제

에너지 연구소는 여러 개의 배터리 셀을 보유하고 있고, 각 셀에는 용량이 매겨져 있습니다. 납품 기준을 맞추려면 모든 셀의 용량이 target 이상이어야 합니다.

용량을 올리는 방법은 병합 공정 하나뿐입니다. 용량이 가장 작은 셀과 두 번째로 작은 셀을 골라 다음 용량의 셀 하나로 합칩니다.

새 셀 용량 = (가장 작은 셀 용량) + (두 번째로 작은 셀 용량) × w

병합에 쓰인 두 셀은 사라지고 새 셀 하나가 그 자리를 대신하므로, 병합할 때마다 셀 개수가 하나씩 줄어듭니다.

모든 셀의 용량을 target 이상으로 만들기 위한 최소 병합 횟수를 반환하세요. 셀이 하나만 남을 때까지 병합해도 기준을 맞출 수 없다면 -1을 반환하세요.

function solution(cells: number[], target: number, w: number): number

예시

첫 번째 예시의 진행 과정입니다.

[2,4,6,8]  → 2 + 4×3 = 14  → [6,8,14]   (최소 용량 6 < 10)
[6,8,14]   → 6 + 8×3 = 30  → [14,30]    (최소 용량 14 ≥ 10) → 2회

제약 조건

• 1 ≤ cells.length ≤ 200,000
• 0 ≤ cells[i] ≤ 1,000,000,000
• 0 ≤ target ≤ 1,000,000,000
• 1 ≤ w ≤ 10

시간 복잡도 목표: O(N log N)

참고: TypeScript에는 내장 우선순위 큐가 없습니다. 직접 min-heap을 구현하거나 정렬된 자료구조를 활용해야 합니다.