[Algo Rhythm🕺💃] BOJ 17528. Two Machines

📚 문제 설명

스케줄링 최적화 회사인 SOPT 에 완료해야 할 n개의 작업 t1, t2, ..., tn 이 있다. SOPT 회사는 두 대의 머신 A 와 B 를 보유하고 있다. 각 작업 ti를 완료하기 위해 SOPT 는 머신 A 와 B 둘 중에 오직 하나를 선택할 수 있다. 작업 ti를 완료하기 위해 머신 A를 선택하면 ai시간이 걸리고 머신 B를 선택하면 bi 시간이 걸린다. 각 머신은 어느 순간에 최대 하나의 작업만 수행할 수 있으며, 한 작업이 시작되면 그 작업을 완료하기 전까지 다른 작업을 그 머신에서 수행할 수 없다. SOPT 는 모든 작업을 완료하기 위한 최소의 완료 시간을 구하고자 한다.

예를 들어, 세 개의 작업이 t1, t2, t3가 주어져 있고 a1 = 2, b1 = 3, a2 = 5, b2 = 3, a3 = 2, b3 = 7라고 하자. 완료 시간을 최소화하기 위해서는 작업 t1, t3는 머신 A에, 작업 t2는 머신 B에 할당한다. 머신 A는 작업 t1, t3를 완료하는데 2 + 2 = 4 시간이 걸리고 머신 B는 작업 t2를 완료하는데 3 시간이 걸린다. 따라서 최소 완료 시간은 4 시간이 된다. n개의 작업 t1, t2, ..., tn 과 각 머신에서 각 작업들을 수행하는 데 걸리는 시간들이 주어질 때, 모든 작업들을 완료하기 위해 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력
입력은 표준입력을 사용한다. 첫 번째 줄에 작업의 개수를 나타내는 양의 정수 n (1 ≤ n ≤ 250)이 주어진다. 다음 n개의 줄에서 i번째 줄에는 두 개의 정수 ai, bi (1 ≤ ai, bi ≤ 250)가 주어진다. 여기서 ai와 bi는 각각 작업 ti를 머신 A와 B에서 완료하는데 걸리는 시간이다.

출력
출력은 표준출력을 사용한다. 모든 작업 t1, t2, ..., tn을 완료하기 위한 최소의 완료시간을 한 줄에 출력한다.

 

🎯 어떻게 풀었나

import java.util.Scanner;

public class BOJ_17528 {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n + 1];
		int[] b = new int[n + 1];
		int[] ab = new int[n + 1];
		int[][] dpA, dpB;
		int totalA = 0 , totalB = 0;
		int ans;
		
		// init
		for(int i = 1; i <= n; i++) {
			a[i] = sc.nextInt();
			b[i] = sc.nextInt();
			ab[i] = a[i] + b[i];
			totalA += a[i];
			totalB += b[i];
		}
		
		sc.close();
		
		dpA = new int[n + 1][totalA + 1];
		dpB = new int[n + 1][totalB + 1];
		
		// dpA
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= totalA; j++) {
				if(ab[i] <= j) {
					dpA[i][j] = Math.max(dpA[i - 1][j], dpA[i - 1][j - ab[i]] + a[i]);
				}
				else {
					dpA[i][j] = dpA[i - 1][j];
				}
			}
		}
		
		// dpB
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= totalB; j++) {
				if(ab[i] <= j) {
					dpB[i][j] = Math.max(dpB[i - 1][j], dpB[i - 1][j - ab[i]] + b[i]); 
				}
				else {
					dpB[i][j] = dpB[i - 1][j];
				}
			}
		}
		
		ans = Math.min(totalA - dpA[n][totalA], totalB - dpB[n][totalB]);
		
		System.out.println(ans);
	}

}

 

🧐 왜 저렇게 풀었나

사실 이 문제는 아래 블로그의 도움을 받아서 해결했다.

https://sbrus1213.tistory.com/3#problemL

 

이 문제를 풀기 전 먼저 생각해야 할 것은 "작업 완료 시간이 최소가 되기 위해서는 A의 수행 시간과 B의 수행 시간의 차이가 최소가 되어야 한다"는 것이다.

이런 경우 우리는 다음과 같은 두 가지 시나리오를 생각할 수 있다.

 

시나리오 1 : A의 수행시간이 B의 수행시간보다 크거나 같고 둘의 차이가 최소인 경우
시나리오 2 : B의 수행시간이 A의 수행시간보다 크거나 같고 둘의 차이가 최소인 경우

 

첫번째 시나리오의 경우 작업 완료 시간은 A의 수행 시간과 같고 두번째 시나리오의 경우 B의 수행 시간과 같을 것이다. 여기서 우리는 첫번째 시나리오의 경우에는 A의 수행시간만, 두번째 시나리오의 경우에는 B의 수행시간만 중요하다는 사실을 알 수 있다.

 

여기까지 도달했으면 시나리오를 보는 관점을 조금 바꾸는 것이 어떨까?

시나리오 1의 경우 모든 작업을 A가, 시나리오 2의 경우 모든 작업을 B가 수행한다고 가정해보자.

시나리오 1의 경우 A의 수행시간이 B의 수행시간보다 크거나 같고 둘의 차이가 최소가 되기 위해서는 A가 담당하고 있는 모든 작업들 중 일부를 B가 수행해야 한다. 이 때 선택해야 하는 작업들은 "B가 수행할 때 A의 수행시간이 가장 많이 감소하는" 작업들이어야 한다. 즉, 가장 많은 A의 수행 시간을 가져오는 것이 최적의 작업이다. 그렇다면 작업 완료 시간은 ( 모든 작업을 A가 수행할 때 걸리는 시간 ) - ( 감소시킬 수 있는 A 수행시간의 최댓값 ) 이다. 시나리오 2의 경우는 반대로 생각하면 된다.

 

여기까지 오면 우리는 이 문제가 0-1 Knapsack problem과 비슷한 모양새를 갖추었다는 사실을 알 수 있다. 더 자세히 말하면 이 문제는 다음과 같이 0-1 Knapsack problem과 대응한다. (아래 예는 시나리오 1을 바탕으로 작성한 것이다.)

 

( item의 개수 ) = ( task의 개수 )

( knapsack에 담을 수 있는 무게 ) = ( A가 모든 작업을 담당할 때 걸리는 수행 시간 )

( item의 무게 ) = ( A가 i번째 task를 수행할 때 걸리는 시간 + B가 i번째 task를 수행할 때 걸리는 시간 )

( item의 가치 ) = ( A가 i번째 task를 수행할 때 걸리는 시간 )

 

이때 왜 item의 무게가 A가 i번째 task를 수행할 때 걸리는 시간 + B가 i번째 task를 수행할 때 걸리는 시간와 대응하는지 직관적으로 이해되지 않을 수도 있다 (나는 이것이 이해되지 않아 오래동안 헤맸다). 이유는 간단하다. 한 작업을 실행할 때 걸리는 A의 수행 시간을 감소시킨다는 것은 같은 작업을 실행할 때 걸리는 B의 수행 시간을 늘린다는 말과 같다. 그렇기 때문에 A가 모든 작업을 담당할 때 걸리는 수행 시간 j는 한 작업을 담당할 때 걸리는 A의 수행시간과 B의 수행시간의 합보다 크거나 같을 때 i번째 작업을 수행할 때 걸리는 A로 수행할 때 걸리는 시간을감소할지 말지(item을 포함하지 말지)를 결정할 수 있다.

시나리오 1, 시나리오 2를 각각 0-1 Knapsack problem으로 구현해서 각 시나리오 마다 작업 완료 시간을 구한 뒤 둘 중 더 작은 것을 구하면 그것이 답이 된다.

 

📖 무엇을 배웠나

생각하는 힘을 기르자!