99클럽 코테 스터디 27일차 TIL - 2861 Maximum Number of Alloys

2861. Maximum Number of Alloys / c++ / Medium / 1시간

문제 및 코드

class Solution {
public:
    bool CheckMakeAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost, unsigned long long count)
    {
        for (int i = 0; i < k; ++i)
        {
            unsigned long long currentBudget = 0;
            for (int j = 0; j < n; ++j)
            {
                unsigned long long needCount = count * composition[i][j];
                if (stock[j] >= needCount) continue;

                currentBudget += (needCount - stock[j]) * cost[j];
            }

            if (currentBudget <= budget) return true;
        }

        return false;
    }
    int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {

        int left = 0, right = 987'654'321, mid, answer;

        while (left <= right)
        {
            mid = (left + right) / 2;

            if (CheckMakeAlloys(n, k, budget, composition, stock, cost, mid))
            {
                answer = mid;
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }

        return answer;
    }
};

접근 방식

배열 / 이분탐색

1. 갯수를 기준으로 이분탐색을 해서, k개의 기계 중 mid 개 만큼의 합금을 budget 이하의 금액으로 만들 수 있는 최대 mid 를 반환하는 문제였다.

생각해 볼 점

1. 이분탐색 치고는 조건이 많이 들어가는 편이었고, 명확한 제한값도 찾지 못해서 꽤나 번거로웠다.
2. count개의 합금을 만들 때, stock[j]개만큼을 빼고 계산해야한는데 그 식을 composition[i][j] * (count - stock[j]) * cost[j] 로 계산해서 틀렸었다. (count개를 만들 때, 합금 한개 당 composition[i][j]만큼의 광석이 들어가므로, 제대로 된 식은 (composition[i][j] * count - stock[j]) * cost[j] 이다.)
3. 별 생각없이 left값을 1로 설정해서 또 한번 틀렸었다. (최대 한개도 만들 수 없으므로, 0으로 설정해야했다.)

해시태그

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL