[Algorithm] 프로그래머스 - 지형 편집

https://school.programmers.co.kr/learn/courses/30/lessons/12984

접근

land의 각 원소는 $0\leq{…}\leq{1,000,000,000}$의 정수이므로, 각 층별로 뭘 해보겠다는 생각은 접어야 한다.

처음엔 추가하는 비용과 제거하는 비용이 가까워질수록 총 비용이 작아질 거라 생각했다.

하지만, 그렇지 않다. 예를 들어, $N=7$의 다음과 같은 land 배열이 주어진다고 가정해보자. 그리고 $P=10$, $Q=10$이다.

land = [
        [1000000000, 0, 1, 0, 1, 0, 1], 
        [1, 0, 1, 0, 1, 0, 1], 
        [1, 0, 1, 0, 1, 0, 1],
        [1, 0, 1, 0, 1, 0, 1],
        [1, 0, 1, 0, 1, 0, 1],
        [1, 0, 1, 0, 1, 0, 1],
        [1, 0, 1, 0, 1, 0, 1]
]

 

land[0][0]이 주어진 입력 가능 범위에서의 최댓값을 갖고 있다.

직관적으로 답은 10,000,000,200임을 알 수 있다.

추가하는 비용과 제거하는 비용이 같을 때, land[0][0]에서 하나씩 제거하는 비용과

그 외 원소에서 일괄적으로 추가하는 비용을 비교하면 하나씩 제거하는 비용이 훨씬 비용이 작기 때문이다.

근데 ‘추가하는 비용과 제거하는 비용이 비슷해질 수록 총비용이 작아진다.’라고 생각하고 문제에 접근하게 되면 논리의 오류가 발생한다.

land[0][0]을 제외한 원소의 갯수는 고작해야 48개이기 때문에 10억에서 하나씩 뺀다고 했을 때,

추가하는 비용과 제거하는 비용이 같아지는 층은 천 만대 단위의 층이 된다.

그렇다면 어떻게 문제에 접근해야 할까?

더 간단하게 생각해본다. 어찌됐든 저찌됐든 총비용이 작아지는 방향으로 층을 탐색하면 된다.

일단 이렇게 큰 입력범위에서 탐색을 진행할 때는 이분탐색을 사용할 수 있다.

이분탐색을 사용하기에 큰 무리가 없으므로 탐색 알고리즘으로는 이분탐색을 사용하겠다.

그리고, 탐색마다 mid를 기준으로 하나 아래에서의 총비용과, 위에서의 총비용을 계산하여 더 작아지는 방향으로 범위를 줄여나가면 된다.

그렇다면 탐색이 진행될 때마다 값을 저장하여 최종적으로 탐색이 완료된 시점의 값이 최소비용이 되는 걸까?

그것도 아니다. 왜냐하면 총비용이 작아지는 방향은 선형적이지 않기 때문이다.

그래서 이전 층에서의 값과 현재 층에서의 값을 항상 비교하면서 최솟값만을 가지도록 보장해야 한다.

소스코드(Java)

public class Solution {
    public long solution(int[][] land, int P, int Q) {
        //총비용(추가비용+제거비용)이 작아지는 방향으로 이분 탐색을 수행한다.
        //(mid-1)지점의 총비용 > (mid+1)지점의 총비용 -> 위로
        //(mid-1)지점의 총비용 < (mid+1)지점의 총비용 -> 아래로

        int max = -1;
        for(int i = 0; i < land.length; i++) {
            for(int j = 0; j < land[0].length; j++) {
                if(max < land[i][j]) {
                    max = land[i][j];
                }
            }
        }

        long start = 0;
        long end = max;
        long mid = (start + end) / 2;
        long result = Long.MAX_VALUE;

        while(start <= end) {

            long removeSum = 0;
            long addSum = 0;
            long removeSumDown = 0;
            long addSumDown = 0;
            long removeSumUp = 0;
            long addSumUp = 0;

            for(int i = 0; i < land.length; i++) {
                for(int j = 0; j < land[0].length; j++) {

                    long remove = (land[i][j] - mid) * Q;
                    if(remove > 0) removeSum += remove;

                    long add = (mid - land[i][j]) * P;
                    if(add > 0) addSum += add;

                    long removeDown = (land[i][j] - (mid - 1)) * Q;
                    if(removeDown > 0) removeSumDown += removeDown;

                    long addDown = ((mid - 1) - land[i][j]) * P;
                    if(addDown > 0) addSumDown += addDown;

                    long removeUp = (land[i][j] - (mid + 1)) * Q;
                    if(removeUp > 0) removeSumUp += removeUp;

                    long addUp = ((mid + 1) - land[i][j]) * P;
                    if(addUp > 0) addSumUp += addUp;
                }
            }
            if(addSumDown + removeSumDown > addSumUp + removeSumUp) start = mid + 1;
            else end = mid - 1;
            mid = (start + end) / 2;
            result = Math.min(addSum+removeSum, result);
        }

        return result == Long.MAX_VALUE ? 0 : result;
    }
}