[BOJ] 2977. 폭탄제조

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

접근 방법

문제를 보고 폭탄의 갯수가 정해져있다면 어떨까 라는 것을 먼저 생각해보았다.

IF) 폭탄을 100개 만들어 본다면 → 가지고 있는 것을 빼고 난 뒤 필요한 제품을 사야 할 것이다.

여기서 중요한 것은 그것을 살 돈이 있는가? 이다.

따라서 폭탄의 갯수의 증감에 따라 답이 도출 되기 때문에 이분 탐색을 사용하기로 했다.

먼저 변수명을 보면 이렇게 되있다. 각 설명은 주석을 달아 두었다.

        static int N;   // 폭탄 제조에 필요한 부품 갯수
    static int M;   // 현재 가지고 있는 돈
    static int[] needList;  // N번째 폭탄의 부품에 폭탄 1개를 만들 때 필요한 갯수
    static int[] haveProduct;   // N번째 폭탄의 부품을 현재 가지고 있는 값
    static Product[] packages;  // N번째 폭탄 부품을 살 때 소형 패키지 & 대형 패키지
    static int ans = 0; // 답

그리고 Product는 객체지향을 살리려고 노력을 해보았다....

class Product{
    Package smallPackage, bigPackage;

    public Product(Package smallPackage, Package bigPackage) {
        this.smallPackage = smallPackage;
        this.bigPackage = bigPackage;
    }
}
class Package{
    int cnt, price;

    public Package(int cnt, int price) {
        this.cnt = cnt;
        this.price = price;
    }
}

위의 내용을 이해했으면 나머지는 코딩을 하면 된다.

근데 여기서 ( 작은 패키지 & 큰 패키지 ) 몇 개씩을 사야 가장 적은 돈 & 필요한 부품의 수

를 만족 하는 지를 결정하는 코드를 어떻게 만들지에 대한 고민을 해보고 풀어보는 것이 좋다.

주의 사항

1. 최대값 ( 즉 Right ) 는 99000이다. 처음에 10000을 하다가 계속 틀려서 고민을 많이했다..

Need Know

1. 이분 탐색

전체 코드 ( Java )

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int N;   // 폭탄 제조에 필요한 부품 갯수
    static int M;   // 현재 가지고 있는 돈
    static int[] needList;  // N번째 폭탄의 부품에 폭탄 1개를 만들 때 필요한 갯수
    static int[] haveProduct;   // N번째 폭탄의 부품을 현재 가지고 있는 값
    static Product[] packages;  // N번째 폭탄 부품을 살 때 소형 패키지 & 대형 패키지
    static int ans = 0; // 답

    public static void main(String[] args) throws IOException {
        set();
        solve();

        bw.flush();
        bw.close();
        br.close();
    }

    static void set() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        needList = new int[N];
        haveProduct = new int[N];
        packages = new Product[N];

        for(int i=0; i< N; i++){
            st = new StringTokenizer(br.readLine());
            needList[i] = Integer.parseInt(st.nextToken());
            haveProduct[i] = Integer.parseInt(st.nextToken());
            packages[i] = new Product(new Package(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())),
                    new Package(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())));
        }
    }

    static void solve() throws IOException {
        int left = 0;
        int right = 99000;

        while(left <= right){
            int limitMoney = M;
            int expectBomb = (left+right) / 2;
            for(int i=0; i< N; i++){
                int needProduct = (needList[i] * expectBomb) - haveProduct[i];
                if(needProduct > 0) {
                    // bigPackage의 최댓값
                    int limit_bigPackage = needProduct / packages[i].bigPackage.cnt;
                    if(needProduct % packages[i].bigPackage.cnt != 0)
                        limit_bigPackage += 1;

                    // smallPackage의 최댓값
                    int limit_smallPackage = needProduct / packages[i].smallPackage.cnt;
                    if(needProduct % packages[i].smallPackage.cnt != 0)
                        limit_smallPackage += 1;

                    int spentMoney = Integer.MAX_VALUE;

                    for(int k=0; k<=limit_bigPackage; k++){
                        for(int z=limit_smallPackage; z>=0; z--){
                            if
                            ( 
                                (k*packages[i].bigPackage.cnt) + (z * packages[i].smallPackage.cnt) >= needProduct
                            )
                            {
                                spentMoney = Math.min(spentMoney,
                                        (k*packages[i].bigPackage.price) + (z * packages[i].smallPackage.price));
                                limit_smallPackage = z; // 이 부분 너무 어렵넹.. ㅠㅠ
                            }else{
                                break;
                            }
                        }
                    }

                    limitMoney -= spentMoney;
                }
                if(limitMoney<0)break;
            }
            if(limitMoney < 0) {
                right = expectBomb-1;
            }else{
                ans = expectBomb;
                left = expectBomb+1;
            }
        }
        bw.write(ans + " ");
    }

}
class Product{
    Package smallPackage, bigPackage;

    public Product(Package smallPackage, Package bigPackage) {
        this.smallPackage = smallPackage;
        this.bigPackage = bigPackage;
    }
}
class Package{
    int cnt, price;

    public Package(int cnt, int price) {
        this.cnt = cnt;
        this.price = price;
    }
}