[BOJ 17528 // C++] Two Machines

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 17528번 문제인 Two Machines이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/17528

17528번: Two Machines

이 문제에서는 주어지는 각 작업을 머신 A와 B로 완료하는 데에 걸리는 시간이 다를 때, A와 B를 이용하여 모든 작업을 가장 빠르게 일을 처리하는 방법을 찾아야한다.

 

A와 B를 그대로 두고 생각하면 복잡하므로, 다음과 같은 작은 문제를 해결하자.

"i 이하의 시간동안 기계 A가 작동할 때, B가 일해야하는 (남은 일) 처리시간의 최솟값을 찾아내기"

 

이 문제는 knapsack 문제를 풀듯이 dp로 해결할 수 있다.

먼저, 0부터 i까지의 index가 있는 배열을 만든다.

초기값은 A가 아무 일도 하지 않은 경우로 채우면 되므로, 모든 일을 B가 맡았을 때의 시간으로 설정한다.

그 이후로, 각각의 작업에 대하여 배열을 시간이 큰 쪽에서 작은 쪽으로 살피면서, 이번 작업을 이 시각에서 A로 할 때와 하지 않을 때를 비교해주면 된다.

 

이 작은 문제를 해결했다면, 남는 것은 i를 가능한 모든 경우의 수로 확장하고(i=min(sumA, sumB)), 각각의 index를 살펴보면서 "A와 B의 작업시간 중 큰 값" 중 최솟값을 찾아 출력하는 것이다.

 

거의 같은 문제로 10982번(행운쿠키 제작소: www.acmicpc.net/problem/10982)이 있으니 관심이 있으면 풀어보는 것도 좋을 것이다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <cmath>
using std::cin; using std::cout;
using std::max;

int machineA[251]; // i번 작업을 A가 할 때 걸리는 시간
int machineB[251]; // i번 작업을 B가 할 때 걸리는 시간
int sumB = 0; // 모든 작업을 B로 처리할 때 걸리는 시간
int working[62751]; // 시간 i만큼을 써서 A가 작업할 때 B가 작업해야 하는 시간

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int N; cin >> N;
    int A, B;
    for (int i = 1;i <= N;i++) {
        cin >> A >> B;
        machineA[i] = A; machineB[i] = B;
        sumB += B;
    }
    for (int i = 0; i <= sumB; i++) {
        working[i] = sumB;
    }
    for (int workIndex = 1;workIndex <= N;workIndex++) {
        for (int workA = sumB; workA >= 0; workA--) {
            int temp1 = workA + machineA[workIndex];
            int temp2 = working[workA] - machineB[workIndex];
            if (working[temp1] > temp2) working[temp1] = temp2;
        }
    }
    int ans = sumB;
    for (int i = 0;i <= sumB;i++) {
        int temp = max(i, working[i]);
        if (ans > temp) ans = temp;
    }
    cout << ans;

    return 0;
}