차원의 보드가 주어지면 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
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 = 4m = 6; int[] x = {2 1 3 1 4}; int[] y = {4 1 2}; System.out.println(minCost(n m x y)); } }
def minCost(nm 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__': nm = 4 6 x = [2 1 3 1 4] y = [4 1 2] print(minCost(nmx y))
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=4m=6; int[] x = {2 1 3 1 4}; int[] y = {4 1 2}; Console.WriteLine(minCost(nm x y)); } }
function minCost( nm 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 = 4m = 6; let x = [2 1 3 1 4]; let y = [4 1 2]; console.log(minCost(nm x y));
산출
42