Two Machines( BOJ 17528 )

문제 : https://www.acmicpc.net/problem/17528

17528번: Two Machines

 

문제 파악하기

2개의 머신(A, B)을 사용하여 N개의 작업을 모두 처리하는데 필요한 시간의 최솟값을 구하는 문제입니다. 각각의 작업은 A와 B 머신 중 하나의 머신에서만 처리될 수 있으며, 선택한 머신에 따라 Ai 또는 Bi만큼의 시간이 소요됩니다. 알고리즘을 단순히 생각하면 두 머신 중 적은 시간이 걸리는 머신에 할당하면 될 것처럼 보입니다. 하지만 만약 4개의 작업이 각각 (1, 3) / (1, 3) / (1, 3) / (1, 3)의 시간이 걸린다고 가정하면 어떨까요? 알고리즘에 따르면 머신 A에 모든 작업을 배치하여 4만큼 시간이 걸립니다. 하지만 4개의 작업 중 1개의 작업을 머신 B에서 처리하고 나머지를 머신 A에서 처리하면 3만큼 시간이 걸릴 수 있습니다. 이렇듯 단순한 그리디 알고리즘으로는 이 문제를 해결할 수 없습니다.

 

문제 해결하기

그렇다면 어떤 방법이 있을까요? 우선은 그리디 알고리즘을 제외한 가장 단순한 방법을 생각해볼 수 있습니다. 바로 브루트포스 알고리즘입니다. 우리는 모든 경우의 수를 탐색하는 브루트포스 알고리즘을 실행하는 sv(idx, mA, mB)라는 재귀 함수를 구현할 수 있습니다.

 

sv(idx, mA, mB) : idx번째 작업까지 진행하는데 머신 A에는 mA만큼, 머신 B에는 mB만큼 작업이 할당된 경우

 

위의 방식은 정답을 구할 수 있지만 작업의 수가 적을 때에만 구할 수 있습니다. 따라서, 위의 재귀함수를 좀 더 효율적으로 바꿔야 합니다. 위의 재귀 함수를 메모이제이션 한다면 dp[idx][mA][mB]와 같이 배열의 형태로 저장할 수 있으며, dp 배열에 저장되는 값은 sv(idx, mA, mB)의 값이 나올 수 있는지 여부에 따라 0 또는 1이 됩니다. 여기서 우리는 0 또는 1이 저장되는 배열의 형태를 바꾸면 좀 더 효율적인 탐색이 될 수 있다는 걸 눈치챌 수 있습니다.

 

만약 dp 배열에 mB의 값을 저장한다면 어떨까요? 그럼 dp 배열은 dp[idx][mA]의 형태로 되며, dp 배열이 가지게 되는 메모리의 최댓값은 250 * 250* 250 = 15,625,000가 되며 충분히 저장하고 탐색할 수 있는 개수가 됩니다. 이처럼 재귀 함수의 효율을 높이기 위해 인수인수의 값을 배열에 저장할 수 있습니다. 이렇게 저장된 dp 배열은 적절하게 점화식을 통해 모든 경우의 수를 탐색하여 배열을 채워나가면 됩니다. dp 배열에 저장되는 값은 머신 B에 할당되는 작업의 양이기 때문에 우리는 다음과 같은 수식을 세울 수 있습니다.

 

dp[idx][mA] = min( dp[idx-1][mA-Ai], dp[idx-1][mA]+Bi ) // (Ai, Bi)는 현재 작업을 처리하는데 걸리는 시간

 

수식에서 dp[idx-1][mA-Ai]는 머신 A에 현재 작업을 할당하는 경우를 의미하며, dp[idx-1][mA]+Bi는 머신 B에 현재 작업을 할당하는 경우를 의미합니다. 그리고 우리는 모든 작업이 처리되는데 필요한 최소 시간을 구하기 때문에 2가지 경우 중 가장 적은 시간이 걸리는 경우를 찾으면 문제를 해결할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#import <stdio.h>
#import <stdlib.h>
#import <utility>
#import <algorithm>
#define NMAX 255
#define MAX 987654321
#define lint long long int
#define PAIR pair<int, int>
using namespace std;
 
int N;
PAIR inp[NMAX];
 
int a, b, tot, ret;
int dp[NMAX][NMAX*NMAX];
 
int main() {
    // input
    scanf("%d", &N);
    for(int i=1;i<=N;i++) scanf("%d %d", &inp[i].first, &inp[i].second);
 
    // dp[i][j]: i번째 작업까지 처리하기 위해 머신 A에 j만큼의 작업이 할당되었을 때, 머신 B에 할당된 작업
    ret = MAX;
    for(int i=1;i<=N;i++) {
        tot += inp[i].first;
 
        for(int j=0;j<=tot;j++) {
            // 현재 작업을 머신 A에 넣기 >> dp[i-1][j-inp[i].first)
            // 현재 작업을 머신 B에 넣기 >> dp[i-1][j] + inp[i].second
            if(j>=inp[i].first) dp[i][j] = min( dp[i-1][j-inp[i].first], dp[i-1][j]+inp[i].second );
            else dp[i][j] = dp[i-1][j]+inp[i].second;
 
            // 결괏값 찾기
            if(i == N) ret = min( ret, max(j, dp[i][j]) );
        }
 
    }
 
    // 출력
    printf("%d", ret);
 
}
/*
4
1 3
1 3
1 3
1 3
ans: 3
*/

후기

N의 범위가 크지 않았지만 시간을 줄이는데 생각이 필요한 문제였습니다. 브루트포스 알고리즘에서 동적 프로그래밍 문제로 변환하는 과정이 나름 재미있던 문제로, 동적 프로그래밍을 연습하는 사람에게 추천하고 싶은 문제입니다.