[백준/BOJ] 백준 17528번 : Two Machines

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

17528번: Two Machines

cache[62501][250]; 에 [A기계에 쌓여있는 시간][해당 인덱스] = B기계에 쌓여있는 시간을 저장하여 bottom-up 방식으로 B기계에 쌓여있는 시간을 최소로 만드는 설계를 하여 값을 채운 뒤, 마지막 인덱스에서 A기계에 쌓여있는 시간과 B기계에 쌓여있는 시간을 비교하는 방식으로 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
vector<int> a;
vector<int> b;
int cache[62501][250]; //[A기계에 쌓여있는 시간][해당 인덱스] = B기계에 쌓여있는 시간

void Pre()
{
	for (int i = 0; i < 62501; i++)
		for (int j = 0; j < 250; j++)
		{
			cache[i][j] = 987654321;
		}
}

//bottom-up DP 이용
int Solve()
{
	cache[a[0]][0] = 0; //A기계에 첫번째 일을 넣을때
	cache[0][0] = b[0]; //B기계에 첫번째 일을 넣을때

	for (int i = 1; i < n; i++)
	{
		//나올 수 있는 모든 A기계의 합을 확인한다
		for (int j = 0; j < 62501; j++)
		{
			int this_a_status = j;

			//이전에 A기계에 해당 값이 나오지 않았을때
			if (cache[this_a_status][i - 1] == 987654321)
				continue;

			//이번 일을 A기계에 넣을때
			cache[this_a_status + a[i]][i] = min(cache[this_a_status + a[i]][i], cache[this_a_status][i - 1]);

			//이번 일을 B기계에 넣을때
			cache[this_a_status][i] = min(cache[this_a_status][i], cache[this_a_status][i - 1] + b[i]);                
		}
	}

	int ret = 987654321;
	for (int i = 0; i < 62501; i++)
	{
		if (cache[i][n - 1] != 987654321)
		{
			ret = min(ret, max(i, cache[i][n - 1]));
		}
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	Pre();

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int ai, bi;
		cin >> ai >> bi;

		a.push_back(ai);
		b.push_back(bi);
	}

	cout << Solve();

	return 0;
}