Minimum Cost to cut a board into squares | Method returns minimum cost to break board into m * n squares ; sort the horizontal cost in reverse order ; sort the vertical cost in reverse order ; initialize current width as 1 ; loop until one or both cost array are processed ; increase current horizontal part count by 1 ; increase current vertical part count by 1 ; loop for horizontal array , if remains ; loop for vertical array , if remains ; Driver program
def minimumCostOfBreaking ( X , Y , m , n ) : NEW_LINE INDENT res = 0 NEW_LINE X . sort ( reverse = True ) NEW_LINE Y . sort ( reverse = True ) NEW_LINE hzntl = 1 ; vert = 1 NEW_LINE i = 0 ; j = 0 NEW_LINE while ( i < m and j < n ) : NEW_LINE INDENT if ( X [ i ] > Y [ j ] ) : NEW_LINE INDENT res += X [ i ] * vert NEW_LINE hzntl += 1 NEW_LINE i += 1 NEW_LINE DEDENT else : NEW_LINE INDENT res += Y [ j ] * hzntl NEW_LINE vert += 1 NEW_LINE j += 1 NEW_LINE DEDENT DEDENT total = 0 NEW_LINE while ( i < m ) : NEW_LINE INDENT total += X [ i ] NEW_LINE i += 1 NEW_LINE DEDENT res += total * vert NEW_LINE total = 0 NEW_LINE while ( j < n ) : NEW_LINE INDENT total += Y [ j ] NEW_LINE j += 1 NEW_LINE DEDENT res += total * hzntl NEW_LINE return res NEW_LINE DEDENT m = 6 ; n = 4 NEW_LINE X = [ 2 , 1 , 3 , 1 , 4 ] NEW_LINE Y = [ 4 , 1 , 2 ] NEW_LINE print ( minimumCostOfBreaking ( X , Y , m - 1 , n - 1 ) ) NEW_LINE