(C#) 지형 편집

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

프로그래머스

 

 Lv4인가? 싶을정도로 아이디어는 쉬웠지만 효율성 테스트에서 벽을 느끼고 말았다.

 

 문제 자체는 이분 탐색으로 쉽게 풀 수 있다.

 임의의 높이 h에서 지형 편집 비용을 그래프로 나타낸다면 위와 같을 것이다. 꼭 이런 형태가 아닐수도 있지만, 대충 이런 형태다.

 

 여기서 임의의 높이 h를 정한다. 해당 위치에서 그래프의 기울기를 구한다.

 만약 기울기가 양수라면, 즉 비용이 높아지고 있다면, h를 왼쪽으로 움직인다.

 만약 기울기가 음수라면, 즉 비용이 낮아지고 있다면, h를 오른쪽으로 움직인다.

 

 이런 아이디어를 적용하면 이분탐색을 쉽게 적용할 수 있다.

 

 다만 효율성 테스트를 통과하지 못했다.

 내 생각에는 임의의 높이 h에서 지형 편집 비용을 계산하는 과정이 너무 오래 걸리는 것 같다.

 지금은 비용 계산에 N^2 만큼의 시간이 걸린다. 이 부분을 더 최적화하는 과정이 필요하다.

코드

using System;

public class Solution {
    public long solution(int[,] land, int p, int q)
    {
        long answer = 0;
        // land의 최소, 최대값
        int min = 1000000000;
        int max = 0;
        for (int i = 0; i < land.GetLength(0); i++)
        {
            for (int j = 0; j < land.GetLength(1); j++)
            {
                if (land[i, j] < min) min = land[i, j];
                if (max < land[i, j]) max = land[i, j];
            }
        }

        // 이분탐색
        while (min < max)
        {
            long min_cost = 0;
            long max_cost = 0;
            int mid = (min + max) / 2;
            for (int i = 0; i < land.GetLength(0); i++)
            {
                for (int j = 0; j < land.GetLength(1); j++)
                {
                    min_cost += (land[i, j] - mid >= 0) ? (long)(land[i, j] - mid) * q : (long)(mid - land[i, j]) * p;
                    max_cost += (land[i, j] - (mid + 1) >= 0) ? (long)(land[i, j] - (mid + 1)) * q : (long)((mid + 1) - land[i, j]) * p;
                }
            }
            if (min_cost < max_cost)
            {
                max = mid;
                answer = min_cost;
            }
            else
            {
                min = mid + 1;
                answer = max_cost;
            }
        }
        return answer;
    }
}