Python에서 k개의 다른 색상으로 울타리를 페인트하는 최소 비용을 찾는 프로그램

<시간/>

N개의 울타리를 K개의 다른 색상으로 칠하고 싶다고 가정해 봅시다. 우리는 두 개의 인접한 울타리가 같은 색상을 가지지 않도록 하면서 비용을 최소화하고자 합니다. 따라서 n번째 행과 k번째 열이 n번째 울타리를 k번째 색상으로 칠하는 비용을 나타내는 N x K 행렬이 있는 경우 이 목표를 달성하는 최소 비용을 찾아야 합니다.

따라서 입력이 다음과 같으면

6	4	5
3	2	7
3	4	5
5	4	4

다음 색상 인덱스(첫 번째 울타리부터 시작) - 5 → 2 → 3 → 4를 선택할 수 있으므로 출력은 14가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=행렬의 행 수
fc :=0, ft :=0
sc :=1, st :=0
행렬의 각 행에 대해 수행
- nfc :=-1, nft :=inf
- nsc :=-1, nst :=정보
- 각 인덱스 i 및 값 t 행에 대해 수행
  - ct :=t +(i가 fc와 같지 않으면 ft, 그렇지 않으면 st)
  - ct <=nft이면
    - nsc :=nfc, nst :=nft
    - nfc :=나, nft :=CT
  - 그렇지 않으면 ct <=nst일 때
    - nsc :=나, nst :=ct
- fc :=nfc, ft :=nft
- sc :=nsc, st :=nst
리턴 피트

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

class Solution:
   def solve(self, matrix):
      n = len(matrix)
      fc, ft = 0, 0
      sc, st = 1, 0
      inf = int(1e18)
      for row in matrix:
         nfc, nft = -1, inf
         nsc, nst = -1, inf
         for i, t in enumerate(row):
            ct = t + (ft if i != fc else st)
            if ct <= nft:
               nsc, nst = nfc, nft
               nfc, nft = i, ct
            elif ct <= nst:
               nsc, nst = i, ct
         fc, ft = nfc, nft
         sc, st = nsc, nst
      return ft

ob = Solution()
matrix = [
   [6, 4, 5],
   [3, 2, 7],
   [3, 4, 5],
   [5, 4, 4]
]
print(ob.solve(matrix))

입력

[
   [6, 4, 5],
   [3, 2, 7],
   [3, 4, 5],
   [5, 4, 4]
]