알고리즘/C++
[C++] BAEKJOON 8901번 화학제품(ACM-ICPC Daejeon 2011)
ssung.k
2019. 8. 2. 21:10
8901번: 화학 제품
문제 상근이는 각기 다른 병에 담긴 세 화학 물질 A, B, C를 가지고 있다. 두 화학 물질을 같은 양만큼 혼합하면, 화학 제품을 얻을 수 있다. A와 B를 혼합하면 AB가 되고, B와 C를 혼합하면 BC, C와 A를 혼합하면 CA가 된다. (A 하나와 B 하나를 혼합하면 AB 하나를 얻게 된다) AB, BC, CA의 가격은 모두 다르다. 따라서, 만드는 화학 제품에 따라서 얻는 이익은 달라진다. 항상 정수 단위 만큼 두 화학 물질을 혼합할 수 있다.
www.acmicpc.net
입력으로 주어지는 모든 숫자는 1000이하이기 떄문에 다음과 같이 어렵지 않게 접근하였습니다.
- ab 혼합물의 수를
0부터a,b의 갯수의 최소값까지 만들어준다. - bc 혼합물의 수를
0부터남은 b의 갯수, c의 최소값까지 만들어준다. - 남은 a 와 c 를 이용해서 ac 혼합물을 만든다.
O(n^2) 의 복잡도로 핵심 알고리즘을 작성하였습니다.
for (int abNum=0;abNum<=min(a,b);abNum++){
for (int bcNum=0;bcNum<=min(b-abNum,c);bcNum++){
int caNum = min(a-abNum,c-bcNum);
maxPrice = max(maxPrice, abNum *abP + bcNum*bcP + caNum *caP);
}
}
이에 대해서 O(n) 으로 해결할 수 있었습니다.
-
ab 혼합물의 수를
0부터a,b의 갯수의 최소값까지 만들어준다. -
ab 혼합물 수를 정한 순간 문제를 새롭게 정의할 수 있습니다.
남아있는 A,B,C 를 이용해서 BC 혼합물과, CA 혼합물로 최대의 이익은 얼마인가
이 경우, BC 혼합물이 비싼 경우, 이를 최대로 만들고 CA 혼합물이 비싼 경우 이를 최대로 만들어주면 됩니다. 따라서 다음과 같이 두 경우의 최대값을 구해줌으로서 해결 했습니다.
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
int T;
cin >> T;
for (int t=0;t<T;t++){
int a,b,c;
int abP,bcP,caP;
cin >> a >> b >> c;
cin >> abP >> bcP >> caP;
int maxPrice = 0;
for (int abNum=0;abNum<=min(a,b);abNum++){
int bcNum = min(b-abNum,c);
int caNum = min(c-bcNum,a-abNum);
maxPrice = max(maxPrice, abNum *abP + bcNum*bcP + caNum *caP);
caNum = min(c,a-abNum);
bcNum = min(b-abNum,c-caNum);
maxPrice = max(maxPrice, abNum *abP + bcNum*bcP + caNum *caP);
}
cout << maxPrice << endl;
}
return 0;
}