문제
https://www.acmicpc.net/problem/8901
문제해설
A, B, C 세개의 화학물질이 주어진다.
그리고 화학물질을 섞었을 때의 가격이 주어진다.
가격은 AB, BC, CA가 존재한다.
화학물들을 적절히 조합하여 최대의 이익을 출력하면 된다.
문제풀이
무식하게 3중 포문으로 푼다면 시간초과가 난다.
문제의 해법은
AB의 개수를 0부터 최대한 만들 수 있는 개수까지
반복문을 돌며 나머지 BC와 CA를 더하는 것이다.
AB의 개수가 고정되면 BC와 CA중에 더 이익이 큰 것을
최대한으로 만들고 남은걸 계산해주면 된다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int t; cin >> t;
while (t--) {
int a, b, c; cin >> a >> b >> c;
int ab, bc, ca; cin >> ab >> bc >> ca;
int res = 0;
for (int i = 0; i <= min(a, b); i++) {
int tmp = ab * i;
int na = a - i;
int nb = b - i;
if (bc < ca) {
tmp += min(na, c) * ca;
int nc = c - min(na, c);
tmp += min(nb, nc) * bc;
}
else {
tmp += min(nb, c) * bc;
int nc = c - min(nb, c);
tmp += min(na, nc) * ca;
}
res = max(res, tmp);
}
cout << res << "\n";
}
return 0;
}