지형 편집

• 인풋이 N*N 크기의 2차원 배열로 들어오지만 별 의미는 없다. 길이가 N^2인 1차원 배열로 들어오는 것과 풀이하는 데에는 아무 차이가 없다.
• 주어진 N^2개의 높이를 정렬한 것을 h라고 하자.
• 모든 칸의 높이를 x로 맞출때의 비용을 cost(x)라고 하자.
• 우선, cost(t)를 최소로 하는 t는 h 배열 안에 있는 수이다.
  • 만약 그렇지 않다면, 즉 t가 h[i-1] < t < h[i] 이라면, 모순이 된다는 것을 쉽게 보일수 있다.
    • 초기 상태에서 t보다 낮은 칸의 갯수는 $i$개, 높은 칸의 갯수는 $n^2-i$ 개이다
    • $h[i-1]$로 만들때의 비용 $cost(h[i-1])$는, $cost(t)$에 비해서, $i$개의 칸은 $t-h[i]$만큼 덜 쌓아야 되고, $n^2-i$개의 칸은 $t-h[i]$만큼 더 깎아야 한다. 그래서
      • $\begin{align} cost(h[i-1]) & = cost(t) - i\times (t-h[i-1])P + (n^2-i)\times (t-h[i-1])Q \\ & = cost(t) - (t-h[i-1])\times((P+Q)i-Qn^2) \end{align}$
        
    • $h[i]$로 만들때의 비용 $cost(h[i])$는, $cost(t)$에 비해서, $i$개의 칸은 $h[i]-t$만큼 더 쌓아야 되고, $n^2-i$개의 칸은 $h[i]-t$만큼 덜 깎아야 한다. 그래서
      • $\begin{align} cost(h[i]) & = cost(t) + i\times (h[i]-t)P - (n^2-i)\times (h[i]-t)Q \\ & = cost(t) + (h[i]-t)\times((P+Q)i-Qn^2) \end{align}$
        
    • 따라서, $(P+Q)i-Qn^2$ 가 양수이면 $cost(h[i-1]) < cost(t)$이고, $(P+Q)i-Qn^2$ 가 음수이면 $cost(h[i]) < cost(t)$. 어느쪽이든 cost(h[x])가 cost(t)보다 작거나 같은 x가 존재한다.
• f(i) = cost(h[i]) - cost(h[i-1]) 라고 하면, 이것은 위에서 했던 것과 비슷한 방법으로 구할 수 있고,
  • $\begin{align} f(i) & = i*(h[i]-h[i-1])P - (n^2-i)*(h[i]-h[i-1])Q \\ & = (h[i]-h[i-1])((P+Q)i-Qn^2) \end{align}$
    
  • f(i) >= 0 인 조건은 $i \leq \frac{Qn^2}{P+Q}$ 이다
• 따라서 $cost(h[i]) = cost(h[0]) + \sum_{n=1}^i{f(n)}$ 가 최대값을 갖는 것은 $i = \frac{Qn^2}{P+Q}$ 일 때이다.
• 이렇게 구한 i를 가지고 t=h[i]를 구하면, cost(t)는 배열을 순회하면서 O(n)에 계산 가능하다.
• 또한, h[i]를 구하는 것은, h를 모두 정렬할 필요도 없이 그냥 i번째로 큰 수만 찾으면 되므로, 이것 또한 이론적으로는 QuickSelect와 같은 선택 알고리즘을 이용해서 O(n)에 구할 수 있고, 전체 시간복잡도는 O(n)이 된다.
  • 그러나 실제 구현은 그냥 O(nlogn)의 built-in sort 함수를 써서 구현했다. python에서는 이편이 O(n)의 선택 알고리즘을 쓰는 것보다 빠르기 때문이다. (선택 알고리즘 참고)

"""Solution code for "Programmers 12984. 지형 편집".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/12984
- Solution link: http://www.teferi.net/ps/problems/programmers/12984
"""

import itertools


def solution(land, P, Q):
    heights = sorted(itertools.chain.from_iterable(land))
    target = heights[Q * len(heights) // (P + Q)]
    return sum((target - h) * (P if target > h else -Q) for h in heights)