Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 보드를 정사각형 조각으로 나누는 최소 절단 비용 구하기

개념

길이 p, 너비 q인 보드가 주어졌다고 가정해 봅시다. 우리는 이 보드를 p×q개의 정사각형 조각으로 나누어야 하며, 이때 발생하는 절단 비용을 최소화하는 것이 목표입니다. 보드의 각 가로·세로 모서리에는 고유한 절단 비용이 부여되어 있습니다. 요약하자면, 전체 비용을 최소화하는 최적의 절단 순서를 찾는 문제입니다.

예시

 C++로 보드를 정사각형 조각으로 나누는 최소 절단 비용 구하기

위 보드를 정사각형으로 나누는 최적의 절단 방법은 다음과 같습니다.

위 경우의 총 최소 비용은 65이며, 아래 단계를 통해 계산됩니다.

초기값 : Total_cost = 0
Total_cost = Total_cost + edge_cost * total_pieces
비용 5 가로 절단 Cost = 0 + 5*1 = 5
비용 5 세로 절단 Cost = 5 + 5*2 = 15
비용 4 세로 절단 Cost = 15 + 4*2 = 23
비용 3 가로 절단 Cost = 23 + 3*3 = 32
비용 3 세로 절단 Cost = 32 + 3*3 = 41
비용 2 가로 절단 Cost = 41 + 2*4 = 49
비용 2 세로 절단 Cost = 49 + 2*4 = 57
비용 2 세로 절단 Cost = 57 + 2*4 = 65

풀이 방법

이러한 유형의 문제는 그리디(Greedy) 알고리즘으로 해결할 수 있습니다. 총 비용을 S라고 하면 S = b₁x₁ + b₂x₂ + … + bₖxₖ 형태로 표현할 수 있으며, 여기서 xᵢ는 특정 모서리의 절단 비용, bᵢ는 대응되는 계수입니다. 계수 bᵢ는 절단 작업이 모두 끝났을 때 해당 모서리(xᵢ) 방향으로 수행된 총 절단 횟수에 의해 결정됩니다.

여기서 중요한 점은 계수들의 합이 항상 일정하다는 사실입니다. 따라서 우리는 S가 최소가 되도록 bᵢ의 분배를 계산해야 합니다. 이를 위한 핵심 전략은 비용이 가장 큰 모서리를 가능한 한 빨리 절단하는 것이며, 이렇게 하면 최적의 S에 도달할 수 있습니다. 만약 비용이 동일한 모서리가 여러 개 있다면, 어느 것을 먼저 잘라도 결과에는 영향을 주지 않습니다.

C++ 프로그램

다음은 위 접근 방식을 구현한 솔루션입니다. 먼저 모든 모서리 절단 비용을 내림차순으로 정렬한 뒤, 비용이 높은 순서부터 낮은 순서로 순회하면서 솔루션을 구성합니다. 각 모서리를 선택할 때마다 해당 방향의 조각 개수(count)를 1씩 증가시키고, 이 값은 매번 해당 모서리의 절단 비용과 곱해져 누적됩니다.

예제 코드

// C++ 프로그램: 보드를 p*q개의 정사각형으로 나누기
#include <bits/stdc++.h>
using namespace std;
int minimumCostOfBreaking(int X1[], int Y1[], int p, int q){
    int res1 = 0;
    sort(X1, X1 + p, greater<int>());
    sort(Y1, Y1 + q, greater<int>());
    int hzntl = 1, vert = 1;
    int i = 0, j = 0;
    while (i < p && j < q){
        if (X1[i] > Y1[j]){
            res1 += X1[i] * vert;
            hzntl++;
            i++;
        }
        else{
            res1 += Y1[j] * hzntl;
            vert++;
            j++;
        }
    }
    int total = 0;
    while (i < p)
        total += X1[i++];
    res1 += total * vert;
    total = 0;
    while (j < q)
        total += Y1[j++];
    res1 += total * hzntl;
    return res1;
}
int main(){
    int p = 6, q = 4;
    int X1[p-1] = {3, 2, 4, 2, 5};
    int Y1[q-1] = {5, 2, 3};
    cout << minimumCostOfBreaking(X1, Y1, p-1, q-1);
    return 0;
}

출력 결과

65