Python에서 보드를 정사각형으로 자르는 최소 비용

길이가 p이고 너비가 q인 보드가 있다고 가정합니다. 우리는 이 보드를 p*q 수의 제곱으로 나누어 깨는 비용이 가능한 한 최소화되도록 해야 합니다. 각 모서리에 대한 절단 비용이 제공됩니다.

따라서 입력이 X_slice =[3,2,4,2,5], Y_slice =[5,2,3]

그러면 출력은 65가 됩니다.

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

• res :=0
• 가로:=1, 세로:=1
• i :=0, j :=0
• i
• X_slice[i]> Y_slice[j]이면
  • res :=res + X_slice[i] * 세로
  • 가로 :=가로 + 1
  • 나는 :=나는 + 1
• 그렇지 않으면
  • res :=res + Y_slice[j] * 가로
  • 세로 :=세로 + 1
  • j :=j + 1

예

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

def minCost(X_slice, Y_slice, m, n):
   res = 0
   X_slice.sort(reverse = True)
   Y_slice.sort(reverse = True)
   horizontal = 1
   vertical = 1
   i = 0
   j = 0
   while i < m and j < n:
      if (X_slice[i] > Y_slice[j]):
         res += X_slice[i] * vertical
         horizontal += 1
         i += 1
      else:
         res += Y_slice[j] * horizontal
         vertical += 1
         j += 1
   total = 0
   while (i < m):
      total += X_slice[i]
      i += 1
   res += total * vertical
   total = 0
   while (j < n):
      total += Y_slice[j]
      j += 1
   res += total * horizontal
   return res
m = 6; n = 4
X_slice = [3,2,4,2,5]
Y_slice = [5,2,3]
print(minCost(X_slice, Y_slice, m-1, n-1))

입력

[3,2,4,2,5],[5,2,3]

출력

65