[C++] BAEKJOON 8901번 화학제품(ACM-ICPC Daejeon 2011)

문제보러가기

8901번: 화학 제품

 

입력으로 주어지는 모든 숫자는 1000이하이기 떄문에 다음과 같이 어렵지 않게 접근하였습니다.

1. ab 혼합물의 수를 0부터 a,b의 갯수의 최소값까지 만들어준다.
2. bc 혼합물의 수를 0 부터 남은 b의 갯수, c의 최소값 까지 만들어준다.
3. 남은 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) 으로 해결할 수 있었습니다.

1. ab 혼합물의 수를 0부터 a,b의 갯수의 최소값까지 만들어준다.

2. 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;
}