크기가 m인 배열이 있다고 가정하고 작은 도시에 있는 m개의 주택을 나타내고 각 주택은 n개의 색상 중 하나로 칠해야 합니다(색상은 1에서 n까지 표시됨). 그리고 일부 주택은 이미 칠해져 있으므로 필요하지 않습니다. 다시 칠합니다. 같은 색으로 칠해진 집들을 이웃이라고 합니다. 우리는 배열 집이 있습니다. 여기서 집[i]은 집의 색상을 나타내고, 색상 값이 0이면 집이 아직 색칠되지 않았음을 나타냅니다. 비용이라는 또 다른 배열이 있습니다. 이것은 비용[i, j]이 색상 j+1로 집 i를 색칠하는 비용을 나타내는 2D 배열입니다. target이라는 또 다른 입력 값도 있습니다. 우리는 이웃의 목표 수와 정확히 일치하는 방식으로 나머지 모든 집을 페인팅하는 데 필요한 최소 비용을 찾아야 합니다. 솔루션을 얻을 수 없으면 -1을 반환합니다.
따라서 입력이 집과 같은 경우 =[0,2,1,2,0] 비용 =[[1,10],[10,1],[10,1],[1,10],[5, 1]] n =2 target =3인 경우 출력은 11이 됩니다. 일부 집은 이미 페인트가 칠해져 있기 때문에 [2,2,1,2,2]와 같은 방식으로 집을 페인트해야 합니다. 세 가지가 있습니다. 이웃, [{2,2}, {1}, {2,2}]. 그리고 첫 번째 집과 마지막 집을 페인트하는 총 비용(10 + 1) =11.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
m :=집의 크기
-
helper() 함수를 정의합니다. i, p_col, grp
가 필요합니다. -
i가 m과 같으면
-
grp가 대상과 같으면 0을 반환하고 그렇지 않으면 inf
-
-
house[i]가 0과 같지 않으면
-
return helper(i + 1, 집[i], grp + (p_col이 집[i]과 같지 않으면 1, 그렇지 않으면 0)
-
-
총계 :=정보
-
범위 1에서 n까지의 col에 대해 다음을 수행하십시오.
-
total =총계의 최소값 및 (cost[i, col - 1] + helper(i + 1, col, grp + (p_col이 col과 같지 않은 경우 1, 그렇지 않은 경우 0)))
-
-
총 반환
-
기본 방법에서 다음을 수행하십시오.
-
as :=도우미(0, -1, 0)
-
ans가 inf가 아닌 경우 반환, 그렇지 않으면 -1
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
def solve(houses, cost, n, target):
m = len(houses)
def helper(i, p_col, grp):
if i == m:
return 0 if grp == target else float('inf')
if houses[i] != 0:
return helper(i + 1, houses[i], grp + int(p_col != houses[i]))
total = float('inf')
for col in range(1, n + 1):
total = min(total, cost[i][col - 1] + helper(i + 1, col, grp + int(p_col != col)))
return total
ans = helper(0, -1, 0)
return ans if ans != float('inf') else -1
houses = [0,2,1,2,0]
cost = [[1,10],[10,1],[10,1],[1,10],[5,1]]
n = 2
target = 3
print(solve(houses, cost, n, target)) 입력
[0,2,1,2,0], [[1,10],[10,1],[10,1],[1,10],[5,1]], 2, 3
출력
11