백준 17528

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

문제 설명

완료해야 하는 작업 리스트가 있고, 두대의 머신 A,B가 있다
머신은 작업마다 걸리는 시간이 다르고 한 작업을 완료하기 전까지 다른 작업을 그 머신에서 수행할 수 없음..
모든 작업을 완료하기 위해 걸리는 시간의 최솟값은..?

ex) 작업이 3개가 있고, a 머신은 각각 2 5 2 시간이 걸리고 b머신은 각각 3 3 7시간이 걸린다 하면 모든 작업을 수행하는 데에는 a b a 순으로 하면 총 4시간이 걸리게 된다..!

문제 풀이

dp를 이용하여 풀 수 있음
dp[i][j]를 생성한다고 하면,
i번째 작업까지 수행하는 데 A가 j분 걸린다 하면 이때 B가 걸리는 최소 시간을 나타낸다..!

이러한 방식으로 저장하게 된다면
dp[i][j]에서 일은 A가 하거나 B가 하거나 둘중 하나이므로

• A가 일하게 된다면 이때 시간은 dp[i-1][j-A수행시간]
• B가 일하게 된다면 수행시간은 dp[i-1][j]+B 수행시간

따라서 둘의 값중 작은 값을 선택하면 된다..!

코드

#include <bits/stdc++.h>
int dp[251][62501]; //[i][j] i번째 일까지 했을 때 A가 j시간이 걸린다면 이때
// 걸리는 B의 최소 시간  
#define MAX 987654321
using namespace std;
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		for(int j=0;j<=n*250;j++){
			dp[i][j] = MAX;
		}
	}
	
	int tmp1,tmp2;
	for(int i=1;i<=n;i++){
		scanf("%d %d",&tmp1,&tmp2);
		dp[i][0] = dp[i-1][0]+tmp2;
		//일을 A가 맡거나 B가 맡거나 둘중 하나
		for(int j=1;j<=n*250;j++){
			if(j-tmp1>=0){
				dp[i][j] = min(dp[i-1][j-tmp1], dp[i-1][j]+tmp2);
			}else{
				dp[i][j] = dp[i-1][j] + tmp2;
			}
			
		}
	}
	int Min =MAX;

	for(int i=1;i<=n*250;i++){
		Min = min(Min, max(dp[n][i] , i));
	}
	printf("%d",Min);
}