백준 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 과 각 머신에서 각 작업들을 수행하는 데 걸리는 시간들이 주어질 때, 모든 작업들을 완료하기 위해 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

문제풀이

사용한 알고리즘 : DP

(1) 코드 7~8

 'dp[i][x] : i번째에서 A가 x만큼 담당할 때 B가 담당하게 되는 최소 일의 양' 으로 설정했습니다.

 0번째 일 -> N-1번째 일 순서로 탐색합니다.

 i번째 일, A가 x만큼 담당하고 있을 때 i+1번째의 점화식은 다음과 같습니다.

    1. i+1 번째 일을 B가 맡지 않는 경우

        dp[i+1][x] = dp[i][x]

    2. i+1 번째 일을 B가 맡을 경우

        dp[i+1][x - (A가 하는 i+1번째 일)] = dp[i][x] + (B가 하는 i+1번째 일)

        이때, dp를 B가 하게되는 '최소' 일 이라고 설정하였으므로, 

        dp[i+1][x - (A가 하는 i+1번째 일)] = min(원래 dp값, dp[i][x] + (B가 하는 i+1번째 일))

(2) 코드 20~30

 초기 dp값을 매우 큰 수로 초기화하고 bottom up 으로 dp 값들을 구해줍니다.

 

(3) 코드 31~32

 max(A가 하는 일,  B가 하는 일) 중 최소가 답이 됩니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int INF = 198654321;
	int N;
	int A[255], B[255];
	// dp[i][x] : i번째에서 A가 x만큼 담당할 때 B가 담당하게 되는 일의 양
	int dp[255][62555];
	int main() {ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	int sum = 0;
	for (int i = 0; i < N; ++i) {
	cin >> A[i] >> B[i];
	sum += A[i];
	}
	fill(&dp[0][0], &dp[0][0] + 255 * 62555, INF);
	dp[0][sum] = 0; // 0번 B가 안맡을 때
	dp[0][sum - A[0]] = B[0]; // 0번 B가 맡을 때
	for (int i = 0; i < N - 1; ++i) {
	for (int x = 0; x <= 62555; ++x) { // 모든 가격
	if (dp[i][x] != INF) {
	dp[i + 1][x] = dp[i][x]; // i+1 B가 안 맡을 때
	dp[i + 1][x - A[i + 1]] = min(dp[i + 1][x - A[i + 1]], dp[i][x] + B[i + 1]); // i+1 B가 맡을 때
	}
	}
	}
	int ans = INF;
	for (int x = 0; x < 62555; ++x) ans = min(ans, max(x, dp[N - 1][x]));
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 17528.cpp hosted with ❤ by GitHub