[Algorithm] programmers/kakao/2018summer/level4/지형 편집

문제 설명

XX 게임에서는 지형 편집 기능을 이용하여 플레이어가 직접 게임 속 지형을 수정할 수 있습니다. 이 게임에서는 1 x 1 x 1 크기의 정육면체 블록을 쌓아 게임 속 지형을 표현합니다. 이때, 블록이 공중에 떠 있거나, 블록 하나가 여러 개의 칸에 걸쳐 놓일 수는 없습니다. 따라서 지형을 편집하기 위해서는 각 칸의 제일 위에 블록 1개를 새로 추가하거나, 제일 위에 있는 블록 한 개를 삭제하는 방식으로 지형을 수정해야 합니다. 이때, 블록 한 개를 새로 추가하거나 삭제하기 위해서는 게임머니를 사용해야 하므로 몇 개의 블록을 추가하고 삭제할지 신중한 선택이 필요합니다.

이 게임을 즐기던 한 플레이어는 N x N 크기의 지역에 자신만의 별장을 만들고 싶어졌습니다. 이를 위해서는 울퉁불퉁한 지형의 모든 칸의 높이가 같아지도록 만들어야 합니다. 이때, 블록 한 개를 추가하려면 P의 비용이, 제거하려면 Q의 비용이 들게 됩니다.
다음은 블록 한 개를 추가할 때 5의 비용이, 제거할 때 3의 비용이 드는 경우, 3 x 3 넓이의 모든 칸의 블록 높이가 같아지도록 만드는 예시입니다.

위 그림과 같이 지형 블록이 놓여 있는 경우 모든 칸의 높이가 3으로 같아지도록 한다면 다음과 같은 모양이 됩니다.

이를 위해서는 3보다 높은 칸의 블록 2개를 제거하고, 3보다 낮은 칸에 총 8개의 블록을 추가해야 하며, 2 x 3 + 8 x 5 = 46의 비용이 들게 됩니다.

그러나 아래 그림과 같이 모든 칸의 높이가 2로 같아지도록 할 때는 6개의 블록을 제거하고, 3개의 블록을 추가하면 6 x 3 + 3 x 5 = 33의 비용이 들게 되며, 이때가 최소비용이 됩니다.

현재 지형의 상태를 나타내는 배열 land와 블록 한 개를 추가하는 데 필요한 비용 P, 블록 한 개를 제거하는 데 필요한 비용 Q가 매개변수로 주어질 때, 모든 칸에 쌓여있는 블록의 높이가 같아지도록 하는 데 필요한 비용의 최솟값을 return 하도록 solution 함수를 완성해 주세요.

제한사항

land는 N x N 크기의 2차원 배열이며, N의 범위는 1 ≤ N ≤ 300입니다.
land의 각 원소는 각 칸에 놓여 있는 블록의 수를 나타내며, 0 이상 10억 이하의 정수입니다.
각 칸에 블록 하나를 추가하는 데는 P, 제거하는 데는 Q의 비용이 들며, P, Q의 범위는 1 ≤ P, Q ≤ 100인 자연수입니다.

접근법

>> 파이썬으로는 정확성 테스트만 다 통과되고 효율성 테스트는 빵점
>> 자바, 씨피피는 통과
>> 확실히 씨피피가 메모리를 덜 먹고, 속도가 빠르구나
>> 그리고 long, long long과 같은 자료형을 고려해야하는 문제가 있구나, 당연하지

>> binary search를 사용하였다. 참고한 글 https://ydeer.tistory.com/78
>> first derivative를 explicit하게 표현할 수 없으니, x, x+1와 같이 인접 포인트에서의 값을 비교하였다.

>> 파이썬으로는 통과시킬 수 없나? 궁금스 
>> 다른 분이 작성한 코드를 보고 공부합시다. >> Hayden Kim 님의 코드를 분석해봅시다
>> minimum_index = int(n*n*Q / (Q+P))
>> ?? binary search의 목적은 결국 위의 mininum_index를 찾기 위함인데
>> 위와 같은 수식으로 바로 찾을 수 있다고? 수학적으로 증명 가능한 것인지 생각해보도록!! future work

코드_효율성 bad

## binary search를 생각하기 이전의 무식한 코드
def solution(land, P, Q):
    n  = len(land)
    maxh = 0
    minh = 0
    for row in land :
        maxh = max(maxh, max(row))
        minh = min(minh, min(row))

    answer = []
    import heapq
    for targeth in range(maxh, minh-1, -1):
        temp = 0
        for row in land:
            for c in row :
                temp += (targeth-c)*P if targeth-c >= 0 else (c-targeth)*Q
        heapq.heappush(answer, temp)
    return heapq.heappop(answer)

코드_Java

import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;

public class Solution {
    int[] land_1d ;
    int n ;
    int myP, myQ;
    ArrayList<Long> answer;
    public long solution(int[][] land, int P, int Q) {
        n = land.length;
        myP = P;
        myQ = Q;
        land_1d = new int[n*n];
        answer = new ArrayList<Long>();
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
               land_1d[i*n+j] = land[i][j];
        Arrays.sort(land_1d);
        int maxh = land_1d[n*n-1];
        int minh = land_1d[0];

        int left = minh;
        int right = maxh;
        int x = (left+right)/2;
        while(left < right){
            if(func(x) < func(x+1)){
                right = x;
            } else  {
                left = x+1;
            }
            x = (left+right)/2;
        }

        return func(x);
    }
    public long func(long t){ // long t vs int t에 따라 결과가 달라집니다
        long result = 0;
        for(int a : land_1d){
            result += (long)((t-a) >= 0 ? (t-a)*myP : (a-t)*myQ);
        }

        return result;
    }

}

코드_cpp

#include <vector>
#include <algorithm>

using namespace std;

int n ;
int myP, myQ;
vector<int> myland;


long long func(long target){
    long long result = 0;
    for(int i = 0; i < n*n; i++){
         result += (long long)(target - myland[i]>= 0 ? (target-myland[i])*myP : (myland[i]-target)*myQ);
    }
    return result;
}
long long solution(vector<vector<int> > land, int P, int Q)
{
    myP = P;
    myQ = Q;
    n = land.size();
    vector<long long> answer;
    for(int i = 0; i < n; i++)
        for(int j =0; j<n; j++)
            myland.push_back(land[i][j]);
    sort(myland.begin(), myland.end());
    int maxh = myland[n*n-1];
    int minh = myland[0];

    int left = minh;
    int right = maxh;
    int x = (left+right)/2;
    while(left < right){

        if(func(x) < func(x+1)){
            right = x ;
        }else {
            left = x+1;
        }
        x = (left+ right)/2;
    }
    return func(x);
}

코드_python_Hayden Kim

import itertools
def solution(land, P, Q):
    flatten = list(itertools.chain.from_iterable(land))
    flatten.sort()
    n = len(land)
    minimum_index = int(n*n*Q / (Q+P))
    layer = flatten[minimum_index]
    return sum([(((layer - v) * P) if v < layer else ((v - layer) * Q)) for v in flatten])