Programmers. 지형편집

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 지형편집

input 범위가 10억이라 당연히 이분탐색일 거라 생각했으나 그냥 전체 지형을 모두 탐색하는 완전탐색 문제였다. 주어진 지형의 최솟, 최댓값을 기준으로 전부 최소, 최대 높이를 통일하는 비용이 양 극단에 해당하고 그 사이 어딘가 지점에 최적점이 존재할 것이다. 즉, 변곡점이 존재한다면 해당 지점이 최소비용 지점이 될 것이고 변곡점이 없다면 양 극단 중 하나가 최소비용 지점일 것이다.

• 지형의 높이를 담은 배열을 생성하고 정렬
• 초기값으로 모든 배열을 최소 높이로 통일했다 가정
• 전체 지형 높이를 담은 배열을 순회하면서 이전과 동일한 높이면 생략하고 동일하지 않다면 이후의 값에 대해선 이전보다 모두 높음을 의미하므로 이전까지의 대해선 현재 높이만큼 쌓고 이후에 대해선 앞서 제거했던 비용만큼 복구시켜야 한다.
• 갱신한 결과가 이전 답보다 작으면 답을 갱신하고 그렇지 않으면 변곡점을 의미하므로 그대로 반복문을 종료한다.

python 코드

def solution(land, P, Q):
    total = 0
    h = []
    R, C = len(land), len(land[0])
    for r in range(len(land)):
        for c in range(len(r)):
            h.append(land[R * r + c])
    h.sort()

    cost = sum(h) - (h[0] * len(h)) * Q
    answer = cost
    for i in range(1, len(h)):
        if h[i - 1] == h[i]:
            continue
        else:
            v = h[i] - h[i - 1]
            cost = cost + P * i * v  - v * Q * (len(h) - i)
            if answer < cost:
                break
            answer = min(answer, cost)
    return answer