프로그래머스 이모티콘 할인행사 C++

할인율이 10, 20, 30, 40로 4가지 밖에 안되며

이모티콘 총 갯수의 상한선도 7개밖에 안된다

 

이는 모든 경우의 수를 탐색해도 4의 7승이므로 제한시간 내에 가능하다.

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> sales; // 세일
vector<pair<int, int>> answer;

// 할인률을 10, 20, 30, 40 까지 경우의 수
// 내림차순으로 해서, 첫 전환점까지 하면 될 것 같은데

// 40 40 40 40 40 40 40
// 10 10 10 10 10 10 10 ~ 40 40 40 40 40 40 40 모든 경우 수

void calculate(vector<vector<int>>& users, vector<int>& emoticons) {

    int totalSubscribe = 0;
    int totalPrice = 0;
    
    for(int i = 0; i < users.size(); i++) {
        
        int price = 0;

        
        for(int j = 0; j < emoticons.size(); j++) {
            if(users[i][0] <= sales[j]) {
                price += emoticons[j] - (emoticons[j] * sales[j] / 100);
            }
        }
        
        if(price >= users[i][1]) {
            totalSubscribe++; // 프리미엄 가입
        } else {
            totalPrice += price;
        }
    }
    
    answer.push_back({totalSubscribe, totalPrice});
}

void dfs(vector<vector<int>>& users, vector<int>& emoticons) {
    
    if(sales.size() == emoticons.size()) {
        calculate(users, emoticons);
        return;
    }
    
    for(int j = 10; j <= 40; j+= 10) {
        sales.push_back(j);
        dfs(users, emoticons);
        sales.pop_back();
    }
}

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    
    dfs(users, emoticons);
    
    sort(answer.begin(), answer.end(), greater<>());
    
    return {answer[0].first, answer[0].second};

}