[BOJ 8901] 화학 제품

 2011 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8901 에서 채점할 수 있습니다.

풀이 )

 1) 최초의 A의 양 = a, B의 양 = b, C의 양 = c, 그리고 최종적으로 완성한 AB의 양 = i, BC의 양 = j인 경우를 생각해보겠습니다.

 그러면 남은 A는 a-i개, C는 c-j개가 있습니다. 이들을 통해 만들 수 있는 CA의 양은 min(a-i,c-j)가 됨은 당연합니다. 굳이 A와 C를 남겨두지 않고 모두 CA로 바꾸는게 이득이기 때문이지요. 따라서 이 경우 답은 ab*i + bc*j + ca*min(a-i,c-j) 가 됩니다.

 이때, AB의 양(i)과 BC의 양(j)은 최대  1000개이기 때문에 i=0~1000, j=0~1000인 경우를 모두 고려해보아도 제한시간내에 답을 구할 수 있습니다.

 풀이1을 이용한 코드 )

// code by RiKang, weeklyps.com
// 2011 ACM-ICPC Daejeon regional - B
// BOJ 8901 화학 제품
 
#include <bits/stdc++.h>
using namespace::std;
 
void solve(){
    int a,b,c,ab,bc,ca;
    scanf("%d %d %d",&a,&b,&c);
    scanf("%d %d %d",&ab,&bc,&ca);
 
    int ans=0;
    for(int i=0; i<=min(a,b); i++)
        for(int j=0; j<=min(b-i,c); j++){
            int k = min(a-i, c-j);
            ans = max(ans, ab*i+bc*j+ca*k);
        }
    
    printf("%d\n",ans);
}
 
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        solve();
    }
    return 0;
}

 2) 1)의 풀이만으로도 제한시간은 맞춰줄 수 있지만, 사실 더 빠른 방법이 존재합니다. AB의 양만 정해져 있어도, BC의 양과 CA의 양을 정할 수 있기 때문입니다.

 AB의 양이 정해져 있다면 문제를 다음과 같이 변형할 수 있습니다.

 "A, B, C의 양이 주어졌을 때, BC와 CA를 만들어서 얻을 수 있는 최대의 이익을 구하시오."

 AB가 빠진 이 문제는 그리디를 통해 O(1)로 답을 구할 수 있습니다. BC의 가치가 CA보다 높다면 BC를 최대한 많이 만들고 그 다음에 CA를 만들어야 하며, 반대로 CA의 가치가 더 높다면 CA를 최대한 많이 만들고 BC를 만드는게 최선이기 때문입니다. (예를 들어, CA를 많이 만들기 위해 BC를 하나 줄여보아도, CA를 하나 더 늘리는 것에 그치기 때문에 위의 두 가지 방법만 고려하면 됨을 증명할 수 있습니다.)

 최종 코드 )

// code by RiKang, weeklyps.com
// 2011 ACM-ICPC Daejeon regional - B
// BOJ 8901 화학 제품
 
#include <bits/stdc++.h>
using namespace::std;
 
void solve(){
    int a,b,c,ab,bc,ca;
    scanf("%d %d %d",&a,&b,&c);
    scanf("%d %d %d",&ab,&bc,&ca);
 
    int ans=0;
    for(int i=0; i<=min(a,b); i++){
        int j = min(b-i, c);
        int k = min(a-i, c-j);
        ans = max(ans, ab*i+bc*j+ca*k);
        k = min(c, a-i);
        j = min(b-i, c-k);
        ans = max(ans, ab*i+bc*j+ca*k);
    }
    
    printf("%d\n",ans);
}
 
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        solve();
    }
    return 0;
}