from itertools import chain
def solution(land, P, Q):
land = sorted(chain.from_iterable(land))
k = len(land) * Q // (P + Q)
h = land[k]
return sum(h - x for x in land[:k])*P + sum(x - h for x in land[k:])*Q
알고리즘
\(f(h)\) : 높이가 \(h\) 일때, 드는 비용
비용의 최솟값을 구하는 문제이니, \(f(h)\) 함수를 미분을 이용해 최솟값을 구할 수 있다.
land:n개의 2차원 배열을 1차원 배열로 펴서 오름차순 정렬
h보다 높이가 낮은 블록k개,h와 높이가 같거나 큰 블록n-k개
\(f(h)\)는 0 이상의 최솟값이 존재하는 V 모양의 자취를 가질 것이고, 미분을 통해 최솟값을 구할 수 있다.
V모양의 자취를 그리는 함수는 모든 구간에서 미분이 불가능 하지만, 자취를 알기에 변곡점이 곧 최소값이 된다.
h보다 낮은 블록의 갯수가 \(\frac{nQ}{P+Q}\) 개일 때 \(f(h)\)는 최소값을 가진다
h = land[k]
from itertools import chain
def solution(land, P, Q):
land = sorted(chain.from_iterable(land))
k = len(land) * Q // (P + Q)
h = land[k]
return sum(h - x for x in land[:k])*P + sum(x - h for x in land[k:])*Q