1642. Furthest Building You Can Reach

[zeikar]

Problem link

https://leetcode.com/problems/furthest-building-you-can-reach

Problem Summary

벽돌의 개수와 사다리의 개수가 주어질 때 빌딩 사이를 가장 멀리 이동할 수 있는 거리를 구하는 문제.
빌딩의 높이가 같거나 낮으면 그냥 이동할 수 있으며, 벽돌은 빌딩 사이의 높이 차이만큼 사용되고 사다리는 높이와 상관없이 한개씩 사용된다.

Solution

그리디로 해결할 수 있다. DP로 해봤는데 bricks의 공간?이 너무 넓어서 메모리 초과가 난다...

빌딩 사이의 높이에 대해 높은 경우에는 사다리를 쓰고 나머지에 대해 벽돌을 쓰는 방식으로 진행하면 된다. 앞에서부터 사다리로 올라가다가 사다리를 다 썼다면 이전에 사용한 높이 중에서 가장 작은 부분을 벽돌로 바꿔치기 하는 방식으로 구현할 수 있다.
이는 Min-Heap 으로 간단하게 구현할 수 있다.

그리디가 되는 이유로는 사다리는 어떤 높이든 사용이 가능하므로 가장 높이 차이가 큰 곳에 사다리를 놓는 게 무조건 이득이다.
또한 귀류법으로도 증명이 가능한데, 더 작은 높이에 사다리를 사용한 경우가 최적이라고 가정할 때 사다리를 더 큰 높이에 사용하면 벽돌이 남게 되고 이는 최적이 아닐 수 있게 된다. (가정에 모순)

다른 풀이

이진 탐색으로도 가능하다.
k 개의 빌딩을 이동할 수 있는가? 에 대한 정답을 구할 수 있으므로 k 값을 이진 탐색으로 찾을 수 있다. 다만 구현은 그리디 방식이 훨씬 간단하다.

Source Code

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        jumps = []
        for i in range(1, len(heights)):
            if heights[i] > heights[i - 1]:
                jumps.append((heights[i] - heights[i - 1], i))

        heap = []  # ladders
        heapify(heap)
        for (jump, idx) in jumps:
            heappush(heap, jump)
            ladders -= 1

            if ladders < 0:  # use bricks
                minjump = heappop(heap)
                bricks -= minjump

            if bricks < 0:
                return idx - 1

        return len(heights) - 1