백준 8901번 - 화학 제품 (Java)

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

 

AB, BC, CA를 만들 수 있는 모든 경우의 수를 확인해봐야하기 때문에 이 문제는 완전탐색 문제로 분류된다.

AB를 0개 만들었을 때, BC를 0개 만들었을 때 -> CA가 만들어지는 개수가 정해진다.

그러므로 AB를 가능한 만큼 만들어보고 각 경우의 수를 만들어보면 된다.

 

A = 4

B = 3

C = 5

 

가 있다고 가정하자. 

 

AB 는 B가 3이므로 3개까지 만들 수 있다.

AB의 개수가 0이면

 

BC는 3개를 만들 수 있다. B를 사용하지 않았기 때문이다.

 

BC를 0개 만들었다면 CA는 4개

BC를 1개 만들었다면 CA는 3개

BC를 2개 만들었다면 CA는 2개

BC를 3개 만들었다면 CA는 1개

 

만들어낼 수 있다. 

 

그리고 AB를 만들어낼 수 있는 최대 수는 MIN(A, B) 이고

AB를 만들고나서 BC를 만들것이므로 BC를 만들어낼 수 있는 최대 수는 MIN(B - AB의개수 , C)

 

이 둘을 만들고 CA를 만들것이므로 CA의 수는 MIN(A - AB의 개수, C - BC의 개수) 가 된다.

 

순열 조합을 생각하면 풀기 힘들고 경우의 수를 생각해야 풀 수 있는 문제였다.

 

import java.io.*;
import java.util.*;

class Main {
    static long[] dp = new long[105];
    static long[] log = new long[105];
    static ArrayList<Long> logArr = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        for(int t = 0; t < T; t++){
            String[] ABC = br.readLine().split(" ");
            int[] abc = new int[3];
            for(int i = 0; i < ABC.length; i++){
                abc[i] = Integer.parseInt(ABC[i]);
            }

            String[] values = br.readLine().split(" ");
            int[] abbccd = new int[3];
            for(int i = 0; i < values.length; i++){
                abbccd[i] = Integer.parseInt(values[i]);
            }

            int A = abc[0];
            int B = abc[1];
            int C = abc[2];

            int AB = abbccd[0];
            int BC = abbccd[1];
            int CA = abbccd[2];
            int answer = 0;
            for(int i = 0; i <= Math.min(A, B); i++){
                for(int j = 0; j <= Math.min(A - i,C); j++) {
                    int k = Math.min(B - i, C - j);

                    answer = Math.max(answer, AB * i + BC * k + CA * j);
                }
            }

            System.out.println(answer);
        }
    }
}