#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> profits; // 모든 경우의 수를 저장할 변수
// 할인율(percent) 정해지면 계산 후 결과를 profits에 저장하는 함수
void addProfit(vector<vector<int>> users, vector<int> emoticons, vector<int> percents) {
int membership = 0;
int money = 0;
// 모든 유저에 대해서 주어진 percents를 활용해 이익 계산
for(auto user : users) {
int spendMoney = 0;
for(int i=0; i<emoticons.size(); i++) {
if (user[0] > percents[i] ) continue;
spendMoney += emoticons[i] * (100 - percents[i]) / 100;
}
// 멤버십을 가입하는지 안하는지 판단
if (spendMoney >= user[1]) {
membership += 1;
}else {
money += spendMoney;
}
}
profits.push_back({membership,money});
}
// 모든 percent의 경우의 수를 만들어 addProfit을 호출하는 함수 (재귀적으로 구현)
void setPercentAndCalc(vector<vector<int>> users, vector<int> emoticons, vector<int> percents) {
if (emoticons.size() == percents.size()) {
addProfit(users, emoticons, percents);
return;
}
for(int i=10; i<=40; i+=10) {
percents.push_back(i);
setPercentAndCalc(users, emoticons, percents);
percents.pop_back();
}
}
// max_element에 활용할 compare 함수 ( 우선순위: membership, 이모티콘 구매금액)
bool compare(vector<int> a, vector<int> b) {
if(a[0] == b[0]) {
return a[1] < b[1];
}
return a[0] < b[0];
}
vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
vector<int> answer;
vector<int> percents;
setPercentAndCalc(users, emoticons, percents);
answer = *max_element(profits.begin(), profits.end(), compare);
return answer;
}
직접 응시하면서 풀었던 문제중에 하나 였다.
당시에 재귀적 구현을 통해 모든 경우의 수를 만드는 것에 실패해서 풀지 못했던 문제다.
모든 경우의 percent를 구하는 방법을 다른문제풀이에 활용할 수 있을 것 같다.