Level 2. 이모티콘 할인행사

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};
}