이모티콘 할인 행사[프로그래머스]

접근법:

가격 조합에 따른 유저들의 이모티콘 가격과 구독 여부를 판별 한다.
가격 조합을 만들기 위해서 dfs 백트래킹을 사용해 중복 가능 조합을 만듭니다.
조합의 크기가 이모티큰의 크기와 같다면 가격을 계산하고 구독여부와 매출 여부를 결정합니다.
각 조합에서 계산된 구독자 수와 매출여부가 최댓값을 갱신 할 수 있다면 합니다.

#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
int max_subscribers = 0;
int max_revenue = 0;
int discount[] = {10, 20, 30, 40};

void dfs(int size, vector<int>& current_discounts, const vector<vector<int>>& users, const vector<int>& emoticons)
{
    if(size == emoticons.size())
    {
        int new_subscribers = 0;
        int total_revenue = 0;
        
        for(const auto& user : users)
        {
            int required_discount = user[0];
            int limit_price = user[1];
            int sum_price = 0;
            
            for (int i = 0; i < emoticons.size(); ++i) {
                if (current_discounts[i] >= required_discount) {
                    sum_price += emoticons[i] * (100 - current_discounts[i]) / 100;
                }
            }
            
            if (sum_price >= limit_price) {
                new_subscribers++;
            } else {
                total_revenue += sum_price;
            }
        }
        
        if (new_subscribers > max_subscribers) {
            max_subscribers = new_subscribers;
            max_revenue = total_revenue;
        } else if (new_subscribers == max_subscribers && total_revenue > max_revenue) {
            max_revenue = total_revenue;
        }
        
        return;
    }
    
    for(int i = 0; i < 4; ++i)
    {
        current_discounts.push_back(discount[i]);
        dfs(size + 1, current_discounts, users, emoticons);
        current_discounts.pop_back();
    }
}

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    vector<int> current_discounts;
    dfs(0, current_discounts, users, emoticons);
    return {max_subscribers, max_revenue};
}

멀쩡한 사각형[프로그래머스]

석유 시추[프로그래머스]