화가의 파티션 문제

난이도 하드
자주 묻는 질문 코드네이션 구글
이진 검색 분열과 정복 동적 프로그래밍 수색조회수 22

문제 정책

Painter 's Partition 문제는 울타리가 있고 화가가 있다는 것을 말합니다. 우리는 화가가 모든 울타리를 칠하는 시간을 최소화하고 싶습니다. 화가가 울타리를 그리는 순서에는 한계가 있습니다. n 명의 화가가 있다고 가정하면 색인 'i'를 가진 화가는 연속적인 순서로만 울타리를 칠할 수 있습니다.

따라서 이것은 첫 번째 화가가 울타리 중 일부를 칠할 것임을 의미합니다. 그런 다음 두 번째 화가는 울타리 중 일부를 그립니다. 모든 화가에게도 마찬가지입니다. 이것은 일부 화가가 페인트 칠할 울타리조차 얻지 못하는 경우에 발생할 수 있습니다.

화가의 파티션 문제

Size of fence : 10 40 40 10 
Time of painting a unit length of fence : 1
Number of Painters : 2
50

설명 : 펜스 1과 2를 첫 번째 화가에게 할당하고 3, 4를 두 번째 화가에게 할당합니다. 첫 번째 화가에게 울타리 1 개를 할당하고 두 번째 화가에게 2, 3, 4를 할당했다면. 그런 다음 첫 번째 화가는 시간 = 10, 두 번째는 시간 = 90이 걸립니다. 모든 화가가 걸리는 최대 시간은 울타리를 칠하는 데 걸린 총 시간입니다. 이는 모든 화가가 동시에 그림을 그리기 시작하기 때문입니다. t = 0. 따라서이 이외의 방법은 더 나쁜 결과를 초래합니다.

Size of fence : 1 100 
Time of painting a unit length of fence : 1 
Number of Painters : 2
100

설명 : 울타리 1을 첫 번째 화가에게 할당하고 2를 두 번째 화가에게 할당합니다. 총 시간은 화가가 걸리는 최대 시간과 같기 때문입니다. 따라서 출력은 100입니다.

화가의 파티션 문제에 대한 접근

우리는 동적 프로그래밍 이 문제를 해결하기 위해. 여기서도 매우 잘 정의 된 동적 프로그래밍 O (1) 시간 복잡도에서 시간의 합을 취하는 기법 (접두사 합). 먼저 한 명의 화가의 문제를 해결하겠습니다. 그런 다음 화가 수 = 2, 3, 4,… n에 대해 상향식으로 해결합니다. i 번째 화가의 문제를 해결하기 위해 i 번째 화가가 울타리 k에서 j까지 페인트하는 데 걸린 시간을 찾을 수 있습니다. 여기서 우리는 i 번째 화가가 울타리 k에서 j까지 페인트하고 1부터 (k-1)까지의 울타리는 (i-1) 화가가 칠한다고 생각했습니다. 이 하위 문제에 대한 답은 (i-1) 화가 또는 i 번째 화가가 걸리는 최대 시간이어야합니다. 이런 식으로 우리는 더 작은 하위 문제를 계속해서 해결합니다. 그런 다음 이러한 작은 하위 문제의 결과를 결합하여 초기 문제 (페인터의 파티션 문제)를 해결합니다.

암호

C ++ 코드 화가의 파티션 문제

#include <bits/stdc++.h>
using namespace std;

long long int solvePaintersPartitionProblem(long long int numberOfPainters, long long int timePerUnit, vector<long long int>& fenceSize){
    int numberOfFences = fenceSize.size();
    if(numberOfFences == 0)return 0;

    vector<long long int> pref(numberOfFences); // stores the prefix sum for faster sum calculation over the range

    pref[0] = (fenceSize[0] * timePerUnit);
    for(int i=1;i<numberOfFences;i++) {
        pref[i] = (fenceSize[i] * timePerUnit);
        pref[i] = (pref[i] + pref[i-1]);
    }

    long long int dp[numberOfPainters][numberOfFences]; // dp[i][j] = minimum time taken for painting j fences by i painters such that they can paint only in contiguous order
    for(int i=0;i<numberOfPainters;i++){
        for(int j=0;j<numberOfFences;j++)
            dp[i][j] = LONG_MAX;
    }

    // Filling the values for first painter
    for(int i=0;i<numberOfFences;i++)dp[0][i] = pref[i];

    // Now solving for painters 2, 3, 4......n
    for(int i=1;i<numberOfPainters;i++){
        for(int j=i;j<numberOfFences;j++){
            for(int k=i;k<=j;k++){
                long long int timeTakenForithPainter = pref[j] - pref[k-1];
                dp[i][j] = min(dp[i][j], max(dp[i-1][k-1], timeTakenForithPainter));
            }
        }
    }

    if(numberOfPainters > numberOfFences)return dp[numberOfFences-1][numberOfFences-1];
    return dp[numberOfPainters-1][numberOfFences-1];
}


int main(){
    int t;cin>>t;
    while(t--){
        long long int numberOfPainters, numberOfFences, timePerUnit;
        cin>>numberOfPainters>>timePerUnit>>numberOfFences;
        vector<long long int> fenceSize(numberOfFences);
        for(int i=0;i<numberOfFences;i++) cin>>fenceSize[i];
        long long int ans = solvePaintersPartitionProblem(numberOfPainters, timePerUnit, fenceSize);
        cout<<ans<<endl;
    }
}
2

2 5 2 // number of painters, time taken paint a unit length of fence and number of fences

1 10  // fences size

10 1 4

1 8 11 3
50 
11

자바 코드 화가의 파티션 문제

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    
    static long solvePaintersPartitionProblem(int numberOfPainters, long timePerUnit, int numberOfFences, long fenceSize[]){
        if(numberOfFences == 0)return 0;
        long pref[] = new long[numberOfFences]; // stores the prefix sum for faster sum calculation over the range
        pref[0] = (fenceSize[0] * timePerUnit);
        for(int i=1;i<numberOfFences;i++) {
            pref[i] = (fenceSize[i] * timePerUnit);
            pref[i] = (pref[i] + pref[i-1]);
        }
    
        long dp[][] = new long[numberOfPainters][numberOfFences]; // dp[i][j] = minimum time taken for painting j fences by i painters such that they can paint only in contiguous order
        for(int i=0;i<numberOfPainters;i++){
            for(int j=0;j<numberOfFences;j++)
                dp[i][j] = Long.MAX_VALUE;
        }
    
        // Filling the values for first painter
        for(int i=0;i<numberOfFences;i++)dp[0][i] = pref[i];
    
        // Now solving for painters 2, 3, 4......n
        for(int i=1;i<numberOfPainters;i++){
            for(int j=i;j<numberOfFences;j++){
                for(int k=i;k<=j;k++){
                    long timeTakenForithPainter = pref[j] - pref[k-1];
                    dp[i][j] = Math.min(dp[i][j], Math.max(dp[i-1][k-1], timeTakenForithPainter));
                }
            }
        }
        if(numberOfPainters > numberOfFences)return dp[numberOfFences-1][numberOfFences-1];
        return dp[numberOfPainters-1][numberOfFences-1];
    }


    public static void main (String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
  int t = sc.nextInt();
        while(t-- > 0){
            int numberOfPainters = sc.nextInt();
            long timePerUnit = sc.nextLong();
            int numberOfFences = sc.nextInt();
            long fenceSize[] = new long[numberOfFences];
            for(int i=0;i<numberOfFences;i++) fenceSize[i] = sc.nextLong();
            long ans = solvePaintersPartitionProblem(numberOfPainters, timePerUnit, numberOfFences, fenceSize);
            System.out.println(ans);
        }
    }
}
2

2 5 2// number of painters, time taken paint a unit length of fence and number of fences 

1 10 // fences size

10 1 4

1 8 11 3
50 
11

복잡성 분석

시간 복잡성: O (N * M ^ 2)

여기서 N = 화가 수 

M = 울타리의 수, 여기서는 i 번째 화가가 보낸 시간을 찾기 위해 접두사 합계를 사용하므로 시간 복잡성을 줄였습니다.

첫 번째 루프는 여러 화가에 걸쳐 실행되고 중첩 된 루프는 펜스 수에 걸쳐 실행됩니다. N = M이면 시간 복잡도 : 화가의 파티션 문제에 대한 O (N ^ 3).

공간 복잡성: O (N * M)

N = 화가 수 

M = 울타리 수, N * M 차원의 2D DP 배열이 있기 때문입니다. 따라서 우리는 화가의 분할 문제에 대한 다항식 공간 복잡성 솔루션을 가지고 있습니다.

Translate »