[백준 8901] 화학 제품 (C++)

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

 

문제

---

상근이는 각기 다른 병에 담긴 세 화학 물질 A, B, C를 가지고 있다. 두 화학 물질을 같은 양만큼 혼합하면, 화학 제품을 얻을 수 있다.

A와 B를 혼합하면 AB가 되고, B와 C를 혼합하면 BC, C와 A를 혼합하면 CA가 된다. (A 하나와 B 하나를 혼합하면 AB 하나를 얻게 된다) AB, BC, CA의 가격은 모두 다르다. 따라서, 만드는 화학 제품에 따라서 얻는 이익은 달라진다. 항상 정수 단위 만큼 두 화학 물질을 혼합할 수 있다.

예를 들어, A를 5만큼, B를 3만큼, C를 7만큼 가지고 있고, 각 화학 제품의 가격은 다음과 같은 경우를 생각해보자.

화학 제품단위 가격

AB	$100
BC	$30
CA	$80

A 하나와 B하나를 혼합해 AB 하나를 만들면 $100을 얻게 된다. 그 다음 B 2개와 C 2개를 혼합하면 $60을 얻게 되고, C 4개와 A 4개를 혼합해 $320을 얻게 된다. 총 이익은 $480이 되고 이 이익이 가능한 이익 중 최댓값이다. 한 화학 물질은 모두 사용하지 않을 수도 있다. 이 예제에서는 C를 하나 사용하지 않았다.

다른 예로, A가 3개, B가 3개, C가 3개가 있고, AB, BC, CA의 가격이 모두 $100인 경우를 생각해보자. A 2개와 B 2개를 혼합해 $200을 얻고, B 1개와 C 1개를 혼합해 $100을 얻을 수 있다. 마지막으로 C 1개와 A 1개를 섞으면 $100을 얻는다. 총 이익은 $400이 되고, 이 값도 가능한 이익 중 최댓값이다.

상근이가 가지고 있는 A, B, C의 양과 AB, BC, CA의 가격이 주어졌을 때, 상근이가 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다. 첫째 줄에는 상근이가 가지고 있는 A, B, C의 양이 주어진다. 둘째 줄에는 AB, BC, CA의 가격이 주어진다. 입력으로 주어지는 모든 숫자는 정수이며, 1보다 크거나 같고, 1,000보다 작거나 같다.

 

출력

---

각 테스트 케이스 마다 최대 이익을 출력한다.

 

문제 풀이

---

브루트포스를 이용한 문제.

AB와 BC를 만드는 개수를 정하면 해당 상황에서 얻어낼 수 있는 최대 이익을 찾아야 하므로 CA의 개수도 자동적으로 정해진다는 것을 이용하여 문제를 푼다.

AB의 개수는 0개부터 A와 B 둘 중 작은 것의 개수까지 만들 수 있다. AB의 개수를 i라 하면 AB를 만들고 남는 A는 A-i이고, 남는 B는 B-i이다.

이 상태에서 BC를 만들면 0개부터 B-i 와 C중 작은 양의 개수까지 만들 수 있다. BC의 개수를 j라 하면 BC를 만들고 남는 C는 C-j이다.

이 상태에서 AC를 만든다면 AC는 0개부터 C-j와 A-i 중 더 더 작은 양의 개수까지 만들 수 있고, 최대 이익을 찾는 문제 이므로 AC는 C-j와 A-i 중 더 작은 것의 개수만큼 만들면 최대가 된다.

이중 반복문에 의해 i와 j를 결정시키면 각각의 상황에서 만들 수 있는 AB, BC, CA의 개수가 정해지고 이익 역시 정해진다. 이 중 최대 이익을 찾아 출력하면 된다.

 

아래는 코드.

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

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

	int T;
	cin >> T;
	for (int t = 0; t < T; t++)
	{
		int A, B, C;
		int costAB, costBC, costCA;
		long long maxCost = 0;
		int currentSelectCost = 0;
		cin >> A >> B >> C;
		cin >> costAB >> costBC >> costCA;
		for (int i = 0; i <= min(A, B); i++)
		{
			currentSelectCost = costAB * i;
			int leftA = A - i;
			int leftB = B - i;
			for (int j = 0; j <= min(leftB, C); j++)
			{
				currentSelectCost += costBC * j;
				int leftC = C - j;
				currentSelectCost += costCA * min(leftC, leftA);
				if (currentSelectCost > maxCost)
				{
					maxCost = currentSelectCost;
				}
				currentSelectCost -= costCA * min(leftC, leftA);
				currentSelectCost -= costBC * j;
			}
		}
		cout << maxCost << "\n";
	}
	return 0;
}