이모티콘 할인행사 150368

문제

접근 방법

이모티콘마다 할인율 4개(10, 20, 30, 40)에 대해 DFS를 시도하면 된다.
4개의 경우에 대해 7번 시도하니
4^7만큼의 경우의 수가 생기며 유저수만큼 팔리는지 확인해주면 1638400만큼의 경우의 수라고 보면 된다.
즉 충분히 해낼 수 있는 경우의 수이므로 DFS로 모든 경우를 확인해주면 된다.

코드

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

using namespace std;
int dx[] = {10, 20, 30, 40};
int retAmount = 0, retMoney = 0;
void dfs(int idx, vector<vector<int>> users, vector<int> emoticons)
{
    if (idx < emoticons.size())
    {
        for (int i = 0; i < 4; ++i)
        {
            for (vector<int> &user : users)
            {
                if (user[0] <= dx[i])
                {
                    int price = emoticons[idx] * (100 - dx[i]) / 100;
                    user[2] += price;
                }
            }
            dfs(idx + 1, users, emoticons);
            for (vector<int> &user : users)
            {
                if (user[0] <= dx[i])
                {
                    int price = emoticons[idx] * (100 - dx[i]) / 100;
                    user[2] -= price;
                }
            }
        }
    }
    else if (idx == emoticons.size())
    {
        int curAmount = 0, curMoney = 0;
        for (vector<int> &user : users)
        {
            if (user[1] <= user[2])
                ++curAmount;
            else
                curMoney += user[2];
        }
        if (curAmount > retAmount)
        {
            retAmount = curAmount;
            retMoney = curMoney;
        }
        else if (curAmount == retAmount && curMoney > retMoney)
        {
            retMoney = curMoney;
        }
    }
}
vector<int> solution(vector<vector<int>> users, vector<int> emoticons)
{
    for (int i = 0; i < users.size(); ++i)
    {
        users[i].push_back(0);
    }
    dfs(0, users, emoticons);

    return {retAmount, retMoney};
}

풀이

문제를 잘 읽으면 풀 수 있다.

이모티콘마다 할인율은 다를 수 있으며, 할인율은 10%, 20%, 30%, 40% 중 하나로 설정됩니다.

이 부분을 놓치고 읽어서 40^7로 해석해버렸다. 그래서 불가능하다고 생각했다가 4^7인 것을 확인하고 가능성을 보았다.
최대 구독자 수와 최대 판매 금액을 갱신해주면서 모든 가능성을 보면 된다.