[LeetCode - Didi labs 기출문제] 265. Paint House II

saurus2 2022. 10. 20. 03:20

265. Paint House II

Hard

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by an n x k cost matrix costs.

For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on...

Return the minimum cost to paint all houses.

Example 1:

Input: costs = [[1,5,3],[2,9,4]]
Output: 5
Explanation:
Paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5; 
Or paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5.

Example 2:

Input: costs = [[1,3],[2,4]]
Output: 5

Constraints:

costs.length == n
costs[i].length == k
1 <= n <= 100
2 <= k <= 20
1 <= costs[i][j] <= 20

문제 풀이

각각의 집 위치에서 색깔에 따른 비용이 주어진다.
각각 인접한 집들에 같은 색이 칠해지지 않고 모든 색을 칠했을때 최소값을 구해야한다.
예시: 세개의 집에 0 1 2 의 색이 칠해질 수 있고, 혹은 0 1 0 도 가능하다.
집의 갯수는 최대 100개이며 페인트 색에 대한 갯수는 최대 20개이다.
시간 복잡도를 계산하면 최악의 경우 100^20가 가능하기 때문에 백트레킹을 사용할때 메모이제이션을 사용해야한다.
메모이제이션을 사용한 백트레킹의 경우 O(n * k * k) 의 시간이 걸린다.
n개의 집에 각각의 색깔 k개를 찾아봐야하고, 각 색깔에 대해서 인접하는지 아닌지 k번을 반복하여 확인해야하기 때문이다.

백트레킹 - 메모이제이션

집 갯수와 페인트의 갯수로 2차원 배열을 만든다.
재귀 함수의 기저조건은 집의 번호가 마지막이면 그 집의 색깔에 대한 비용을 반환한다.
또한 만약 현재 집위치와 현재 색깔이 메모에 저장이 되어있으면 재귀 함수를 종료하기 위해 해당 메모의 값을 반환한다.
현재 집위치의 비용값을 정수 최대값으로 설정하고, 모든 색깔에 대해 재귀함수 호출을 하게된다.
이때, 자기 자신의 색은 제외해야한다.
백트레킹을 진행하고 반환된 값을 현재 위치집의 비용값에 넣어야 하는데, 최소 값을 찾아 넣자.
마찬가지로 메모에 현재 위치의 최소 페인트 비용과 이전에 처리된 비용을 더해서 넣는다.
이 값도 마찬가지로 반환해준다.
백트레킹을 호출할때 0번 위치에서 모든 색깔 비용을 기준으로 호출해줘야한다.
그리고 각각의 백트레킹 반환 값들과 비교하여 최소값을 반환한다.

백트레킹 - LRU Cache

LRU Cache를 사용하면 메모이제이션을 쉽게 구현할 수 있다.
백트레킹의 설계는 위와 같다.
이와 별개로, 메모 매열을 따로 생성하여 저장해줄 필요없이, 해당 집위치와 색깔에 대한 비용을 반환한다.
반환만 제대로 해준다면, 현재 집 위치와 색깔의 인덱스를 자동으로 메모이제이션 해준다.
예를 들어, 집의 위치 3이고 색깔이 2인 비용이 이미 처리되어서 반환이 되었다면 LRU Cache는
다시 집의 위치 3, 색깔 2인 비용을 접근할때 가장 최소값을 재귀 함수 호출 없이 받을 수 있다.
다른 구현은 위와 동일하다.

다이나믹 프로그래밍 - O(n * k)

다이나믹 프로그래밍을 사용하면 시간 복잡도를 줄일 수 있다.
집 위치 1부터 반복문을 진행한다.
사용할 최소값은 두개이다, 그 이유는 현재 집위치에서 이전 선택 되었던 최소 색깔의 값을 사용하면 안되기 때문이다.
1, 2번 최소값을 None으로 만들어 놓고 색깔을 모두 탐색한다.
만약 1번 최소값이 없거나 이전 집의 첫번째 최소 색깔의 비용이 지금 색깔의 이전 집 비용보다 작으면,
2번 최소값에 현재 1번 최소값을 할당하고, 1번 최소값은 현재 색깔로 설정한다.
만일 이에 해당하지 않고, 두번째 최소 색깔이 비어있거나 이전집의 두번째 최소 색깔의 비용이 이전 집 현재 색깔의 비용보다 크다면
2번 최소값을 현재 색깔로 설정한다.
이러한 최소 색깔을 탐색하는 이유는, 색깔을 선택할때 현재 위치에서 이전 색깔 선택과 다른 색 중 최소 비용을 선택해야하기 때문이다.
그리고, 마지막으로 색깔에 따라 1번 최소 색깔이 아니면 현재 집 위치 색깔 위치에 이전 1번 최소 색깔 비용을 더해준다.
그게 아니라면 2번 최소 색깔 비용을 더해준다.
그 후, DP 배열의 마지막 줄의 최소 값을 반환하면 끝난다.

소스 코드

백트레킹

# memo 
class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:
        n = len(costs)
        if n == 0: return 0
        k = len(costs[0])
        memo = [[0] * k for _ in range(n)]
        
        def bt(house_num, color):
            if house_num == n - 1:
                memo[house_num][color] = costs[house_num][color]
                return costs[house_num][color]
            
            if memo[house_num][color]:
                return memo[house_num][color]
            
            cost = inf
            for nxt in range(k):
                if nxt == color: continue
                cost = min(cost, bt(house_num + 1, nxt))
            
            memo[house_num][color] = costs[house_num][color] + cost
            return costs[house_num][color] + cost
        
        cost = inf
        for c in range(k):
            cost = min(cost, bt(0, c))
        return cost

백트레킹 @lru_cache

# memo lru_cache
class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:
        n = len(costs)
        if n == 0: return 0
        k = len(costs[0])
        
        @lru_cache(maxsize=None)
        def bt(house_num, color):
            if house_num == n - 1:
                return costs[house_num][color]
            
            cost = inf
            for nxt in range(k):
                if nxt == color: continue
                cost = min(cost, bt(house_num + 1, nxt))
            
            return costs[house_num][color] + cost
        
        cost = inf
        for c in range(k):
            cost = min(cost, bt(0, c))
        return cost

다이나믹프로그래밍

# dp
class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:
        n = len(costs)
        if n == 0: return 0
        k = len(costs[0])
        
        for house_num in range(1, n):
            min_col = sec_min_col = None
            for c in range(k):
                cost = costs[house_num - 1][c]
                if min_col is None or cost < costs[house_num - 1][min_col]:
                    sec_min_col = min_col
                    min_col = c
                elif sec_min_col is None or cost < costs[house_num - 1][sec_min_col]:
                    sec_min_col = c
            for c in range(k):
                if c != min_col:
                    costs[house_num][c] += costs[house_num - 1][min_col]
                else:
                    costs[house_num][c] += costs[house_num - 1][sec_min_col]
        return min(costs[-1])

저작자표시 (새창열림)