[Summer/Winter Coding(~2018)] 지형 편집

⭐️ 지형 편집

문제를 처음 접했을 때 백준에서 풀어본 문제랑 거의 동일하다는 것을 느꼈습니다.

문제는 높이는 최소 1, 최대 300으로 제한하고 있습니다. 당연히 높이마다 탐색해서 최소값을 구하는 것 보다 최소 높이와 최대 높이를 정해서 이분탐색하는게 더 빠를 것 같습니다.

 

def solution(land, P, Q):
    answer = 1e9
    min_height = 1e9
    max_height = 0
    for i in range(len(land)):
        for j in range(len(land[0])):
            max_height = max(max_height, land[i][j])     
            min_height = min(min_height, land[i][j])

    def find_value ( h, land):
        cnt =0 
        for i in range(len(land)):
            for j in range(len(land[0])) :
                if h > land[i][j]:
                    cnt += (h - land[i][j]) * P
                elif h < land[i][j] :
                    cnt += (land[i][j] - h) * Q
                else: 
                    continue                 
        return cnt

    while True:

        mid = (min_height + max_height) // 2

        midMinusOneValue = find_value (mid - 1, land)

        mid_value = find_value (mid , land)
        midPlusOneValue = find_value(mid + 1, land)

        if mid_value <= midPlusOneValue and mid_value <= midMinusOneValue :
            answer = mid_value
            break
        elif midMinusOneValue < mid_value:
            max_height = mid - 1
        elif midPlusOneValue < mid_value:
            min_height = mid + 1
    return answer

효율성 0ㅋㅋㅋㅋㅋ

 

정답을 찾으려면 좌우 높이의 계산값보다 더 최솟값 즉 변곡점을 찾으면 됩니다.

이분탐색이 효율성에서 실패해서 일층부터 쌓아 올리는 방식으로 블로그 글들을 읽으면서 따라해보았습니다.

 

def solution(land, P, Q):
    lst = []
    for i in land:
        lst += i
    lst = sorted(lst)

    n = len(lst)
    answer = sum(lst)*Q
    cost = (sum(lst) - lst[0]*n )*Q  
    answer = min(answer, cost)

    for i in range(1, n):
        if lst[i] != lst[i-1]:
            cost += (P * i * (lst[i]-lst[i-1])) - (Q * (n-i) * (lst[i]-lst[i-1]))

            answer = min(answer, cost)

    return answer