보드를 사각형으로 자르는 데 드는 최소 비용
차원의 보드가 주어지면 n×m n×m 정사각형으로 잘라야 합니다. 수평 또는 수직 가장자리를 따라 절단하는 비용은 두 가지 배열로 제공됩니다.
- 엑스[] : 수직 가장자리(세로 방향)를 따라 비용이 절감됩니다.
- 그리고[] : 가로 가장자리(폭 방향)를 따라 비용이 절감됩니다.
보드를 최적의 정사각형으로 자르는 데 필요한 최소 총 비용을 구하십시오.
예:
입력: x[] = [2 1 3 1 4] y[] = [4 1 2] n = 4 m = 6
산출: 42
설명:
처음에는 아니오. 수평 세그먼트 수 = 1 & no. 수직 세그먼트 수 = 1.
정사각형으로 자르는 최적의 방법은 다음과 같습니다.
(x에서) 4개 선택 -> 수직 절단 비용 = 4 × 수평 세그먼트 = 4
이제 수평 세그먼트 = 1 수직 세그먼트 = 2입니다.
(y에서) 4 선택 -> 수평 절단 비용 = 4 × 수직 세그먼트 = 8
이제 수평 세그먼트 = 2 수직 세그먼트 = 2입니다.
(x에서) 3개 선택 -> 수직 절단 비용 = 3 × 수평 세그먼트 = 6
이제 수평 세그먼트 = 2 수직 세그먼트 = 3입니다.
(x에서) 2개 선택 -> 수직 절단 비용 = 2 × 수평 세그먼트 = 4
이제 수평 세그먼트 = 2 수직 세그먼트 = 4입니다.
(y에서) 2 선택 -> 수평 절단 비용 = 2 × 수직 세그먼트 = 8
이제 수평 세그먼트 = 3개의 수직 세그먼트 = 4입니다.
(x에서) 1개 선택 -> 수직 절단 비용 = 1 × 수평 세그먼트 = 3
이제 수평 세그먼트 = 3개의 수직 세그먼트 = 5입니다.
(x에서) 1개 선택 -> 수직 절단 비용 = 1 × 수평 세그먼트 = 3
이제 수평 세그먼트 = 3개의 수직 세그먼트 = 6입니다.
(y에서) 1 선택 -> 수평 절단 비용 = 1 × 수직 세그먼트 = 6
이제 수평 세그먼트 = 4개의 수직 세그먼트 = 6입니다.
따라서 총 비용 = 4 + 8 + 6 + 4 + 8 + 3 + 3 + 6 = 42입니다.입력: x[] = [1 1 1] y[] = [1 1 1] n = 4 m = 4
산출: 15
설명:
처음에는 아니오. 수평 세그먼트 수 = 1 & no. 수직 세그먼트 수 = 1.
정사각형으로 자르는 최적의 방법은 다음과 같습니다.
(y에서) 1 선택 -> 수평 절단 비용 = 1 × 수직 세그먼트 = 1
이제 수평 세그먼트 = 2 수직 세그먼트 = 1입니다.
(y에서) 1 선택 -> 수평 절단 비용 = 1 × 수직 세그먼트 = 1
이제 수평 세그먼트 = 3개의 수직 세그먼트 = 1입니다.
(y에서) 1 선택 -> 수평 절단 비용 = 1 × 수직 세그먼트 = 1
이제 수평 세그먼트 = 4개의 수직 세그먼트 = 1입니다.
(x에서) 1개 선택 -> 수직 절단 비용 = 1 × 수평 세그먼트 = 4
이제 수평 세그먼트 = 4개의 수직 세그먼트 = 2입니다.
(x에서) 1개 선택 -> 수직 절단 비용 = 1 × 수평 세그먼트 = 4
이제 수평 세그먼트 = 4개의 수직 세그먼트 = 3입니다.
(x에서) 1개 선택 -> 수직 절단 비용 = 1 × 수평 세그먼트 = 4
이제 수평 세그먼트 = 4 수직 세그먼트 = 4
따라서 총 비용 = 1 + 1 + 1 + 4 + 4 + 4 = 15입니다.
목차
- [순진한 접근 방식] 모든 순열 시도 - O((n+m)!×(n+m)) 시간 및 O(n+m) 공간
- [예상 접근 방식] 그리디(Greedy) 기법 활용 - O(n(log n)+m(log m)) 시간과 O(1) 공간
[순진한 접근 방식] 모든 순열 시도 - O((n+m)!×(n+m)) 시간 및 O(n+m) 공간
아이디어는 주어진 컷의 가능한 모든 순열을 생성한 다음 각 순열의 비용을 계산하는 것입니다. 마지막으로 그 중 최소 비용을 반환합니다.
메모: 순열의 수가 (m+n-2)!로 계승 증가하기 때문에 이 접근 방식은 더 큰 입력에는 적합하지 않습니다.
각 순열에 대해 O(m+n) 시간으로 비용을 계산해야 합니다. 따라서 전체 시간 복잡도는 O((m+n−2)!×(m+n))가 됩니다.
[예상 접근 방식] 그리디(Greedy) 기법 활용 - O(n(log n)+m(log m)) 시간과 O(1) 공간
아이디어는 가장 비싼 절단을 먼저 사용하는 것입니다. 탐욕스러운 접근 . 각 단계에서 가장 높은 비용 절감을 선택하면 한 번에 여러 부분에 영향을 미쳐 향후 비용이 절감된다는 것이 관찰되었습니다. 수직(x) 및 수평(y) 절감 비용을 내림차순으로 정렬한 후 반복적으로 더 큰 비용을 선택하여 비용 절감을 극대화합니다. 나머지 컷은 모든 섹션이 최적으로 분할되도록 별도로 처리됩니다.
컷을 하면 어떻게 되나요?
- 수평 절단 → 너비를 가로질러 절단하므로 수평 스트립 수가 증가합니다(hCount++). 그러나 수평 절단은 모든 수직 세그먼트를 통과해야 하기 때문에 비용에 vCount(수직 스트립 수)가 곱해집니다.
- 수직 절단 → 높이를 가로질러 절단하므로 수직 스트립 수가 증가합니다(vCount++). 그러나 수직 절단은 모든 수평 세그먼트를 통과해야 하기 때문에 비용에 hCount(수평 스트립 수)가 곱해집니다.
문제 해결 단계:
- x 및 y 배열을 모두 내림차순으로 정렬합니다.
- 가장 큰 값에서 시작하여 더 작은 값으로 이동하는 x와 y에 각각 하나씩 두 개의 포인터를 사용합니다.
- hCount 및 vCount를 유지하여 각 컷이 영향을 미치는 세그먼트 수를 추적하고 그에 따라 업데이트합니다.
- x와 y 모두 처리되지 않은 삭감이 있는 동안 반복하여 전체 비용을 최소화하기 위해 항상 더 큰 비용을 선택합니다.
- x에 남은 컷이 있는 경우 hCount 배수로 처리합니다. 마찬가지로 vCount를 사용하여 나머지 y 컷을 처리합니다.
- 다음 공식을 사용하여 각 단계에서 총 비용을 누적합니다. 비용 절감 * 비용을 최소화하는 영향을 받는 부품 수.
#include #include #include using namespace std ; int minCost ( int n int m vector < int >& x vector < int >& y ) { // Sort the cutting costs in ascending order sort ( x . begin () x . end ()); sort ( y . begin () y . end ()); int hCount = 1 vCount = 1 ; int i = x . size () - 1 j = y . size () - 1 ; int totalCost = 0 ; while ( i >= 0 && j >= 0 ) { // Choose the larger cost cut to // minimize future costs if ( x [ i ] >= y [ j ]) { totalCost += x [ i ] * hCount ; vCount ++ ; i -- ; } else { totalCost += y [ j ] * vCount ; hCount ++ ; j -- ; } } // Process remaining vertical cuts while ( i >= 0 ) { totalCost += x [ i ] * hCount ; vCount ++ ; i -- ; } // Process remaining horizontal cuts while ( j >= 0 ) { totalCost += y [ j ] * vCount ; hCount ++ ; j -- ; } return totalCost ; } int main () { int n = 4 m = 6 ; vector < int > x = { 2 1 3 1 4 }; vector < int > y = { 4 1 2 }; cout < < minCost ( n m x y ) < < endl ; return 0 ; }
Java import java.util.Arrays ; class GfG { static int minCost ( int n int m int [] x int [] y ) { // Sort the cutting costs in ascending order Arrays . sort ( x ); Arrays . sort ( y ); int hCount = 1 vCount = 1 ; int i = x . length - 1 j = y . length - 1 ; int totalCost = 0 ; while ( i >= 0 && j >= 0 ) { // Choose the larger cost cut to // minimize future costs if ( x [ i ] >= y [ j ] ) { totalCost += x [ i ] * hCount ; vCount ++ ; i -- ; } else { totalCost += y [ j ] * vCount ; hCount ++ ; j -- ; } } // Process remaining vertical cuts while ( i >= 0 ) { totalCost += x [ i ] * hCount ; vCount ++ ; i -- ; } // Process remaining horizontal cuts while ( j >= 0 ) { totalCost += y [ j ] * vCount ; hCount ++ ; j -- ; } return totalCost ; } public static void main ( String [] args ) { int n = 4 m = 6 ; int [] x = { 2 1 3 1 4 }; int [] y = { 4 1 2 }; System . out . println ( minCost ( n m x y )); } }
Python def minCost ( n m x y ): # Sort the cutting costs in ascending order x . sort () y . sort () hCount vCount = 1 1 i j = len ( x ) - 1 len ( y ) - 1 totalCost = 0 while i >= 0 and j >= 0 : # Choose the larger cost cut to # minimize future costs if x [ i ] >= y [ j ]: totalCost += x [ i ] * hCount vCount += 1 i -= 1 else : totalCost += y [ j ] * vCount hCount += 1 j -= 1 # Process remaining vertical cuts while i >= 0 : totalCost += x [ i ] * hCount vCount += 1 i -= 1 # Process remaining horizontal cuts while j >= 0 : totalCost += y [ j ] * vCount hCount += 1 j -= 1 return totalCost if __name__ == '__main__' : n m = 4 6 x = [ 2 1 3 1 4 ] y = [ 4 1 2 ] print ( minCost ( n m x y ))
C# using System ; class GfG { public static int minCost ( int n int m int [] x int [] y ) { // Sort the cutting costs in ascending order Array . Sort ( x ); Array . Sort ( y ); int hCount = 1 vCount = 1 ; int i = x . Length - 1 j = y . Length - 1 ; int totalCost = 0 ; // Process the cuts in greedy manner while ( i >= 0 && j >= 0 ) { // Choose the larger cost cut to // minimize future costs if ( x [ i ] >= y [ j ]) { totalCost += x [ i ] * hCount ; vCount ++ ; i -- ; } else { totalCost += y [ j ] * vCount ; hCount ++ ; j -- ; } } // Process remaining vertical cuts while ( i >= 0 ) { totalCost += x [ i ] * hCount ; vCount ++ ; i -- ; } // Process remaining horizontal cuts while ( j >= 0 ) { totalCost += y [ j ] * vCount ; hCount ++ ; j -- ; } return totalCost ; } public static void Main () { int n = 4 m = 6 ; int [] x = { 2 1 3 1 4 }; int [] y = { 4 1 2 }; Console . WriteLine ( minCost ( n m x y )); } }
JavaScript function minCost ( n m x y ) { // Sort the cutting costs in ascending order x . sort (( a b ) => a - b ); y . sort (( a b ) => a - b ); let hCount = 1 vCount = 1 ; let i = x . length - 1 j = y . length - 1 ; let totalCost = 0 ; while ( i >= 0 && j >= 0 ) { // Choose the larger cost cut to // minimize future costs if ( x [ i ] >= y [ j ]) { totalCost += x [ i ] * hCount ; vCount ++ ; i -- ; } else { totalCost += y [ j ] * vCount ; hCount ++ ; j -- ; } } // Process remaining vertical cuts while ( i >= 0 ) { totalCost += x [ i ] * hCount ; vCount ++ ; i -- ; } // Process remaining horizontal cuts while ( j >= 0 ) { totalCost += y [ j ] * vCount ; hCount ++ ; j -- ; } return totalCost ; } // Driver Code let n = 4 m = 6 ; let x = [ 2 1 3 1 4 ]; let y = [ 4 1 2 ]; console . log ( minCost ( n m x y ));
산출
42퀴즈 만들기
