Level 2. 이모티콘 할인행사
이모티콘의 개수가 다행이 7개 이하여서, 그냥 모든 할인율의 조합을 구해 풀라는 문제이다.
- 조합은 시작점과 레벨이 핵심인데, 이 문제에선 중복 조합이므로 레벨만 DFS 함수에 전달하면 된다.
이후, 이모티콘 플러수 가입자수를 키로 하고 최대 판매액을 값으로 하는 map을 만들어 계산하면 된다.
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
void rDFS(int depth, vector<float>& comb, vector<vector<float>>& result)
{
if (comb.size() <= depth)
{
result.emplace_back(comb);
return;
}
for (float d : {0, 10, 20, 30, 40})
{
comb[depth] = d;
rDFS(depth + 1, comb, result);
}
}
vector<int> solution(vector<vector<int>> users, vector<int> emoticons)
{
map<int, int> mp;
vector<float> v(emoticons.size());
vector<vector<float>> result;
rDFS(0, v, result);
for (vector<float>& comb : result)
{
int nEmoticonPlus = 0;
int revenue = 0;
for (vector<int>& user : users)
{
float total = 0;
bool bEmoticonPlus = false;
for (int i = 0; i < comb.size(); ++i)
{
if (user[0] <= comb[i])
{
total += emoticons[i] * (100 - comb[i]) / 100;
if (user[1] <= total)
{
bEmoticonPlus = true;
break;
}
}
}
if (bEmoticonPlus)
++nEmoticonPlus;
else
revenue += total;
}
mp[nEmoticonPlus] = max(mp[nEmoticonPlus], revenue);
}
return {mp.rbegin()->first, mp.rbegin()->second};
}
'자료구조 & 알고리즘 > 프로그래머스' 카테고리의 다른 글
Level 3. 부대복귀 (0) | 2023.09.10 |
---|---|
Level 2. N-Queen (0) | 2023.09.06 |
Level 3. 스티커 모으기(2) (0) | 2023.09.05 |
Level 3. 경주로 건설 (0) | 2023.09.04 |
Level 3. 보석 쇼핑 (0) | 2023.09.03 |