[Programmers] 이모티콘 할인 행사 [C++]

https://school.programmers.co.kr/learn/courses/30/lessons/150368

문제 이해 및 분석

1. 서비스 가입자 수를 최대한 늘리는 것이 1목표
2. 그 후, 이모티콘 판매액을 최대한 늘리는 것이 2 목표
   1. 즉, 가입 0명, 매출액 10 보다 가입 1명 매출액 0 이 우선순위 이다.
3. 각 사용자마다 구매 할인율이 있다 → 구매 할인율을 넘어가는 이모티콘만 구매.
4. 구매한 이모티콘 가격의 총 합이 기준점을 넘어갈 경우, 이모티콘 구매를 취소하고 서비스 가입
5. 이모티콘 할인율은 각각 10, 20, 30, 40 중 하나로 정할 수 있다

코드 설명

코드는 크게 세 단계로 나눌 수 있다:

1. 할인율 조합 생성: 모든 이모티콘에 대해 가능한 할인율 조합을 생성.
2. 각 조합에 대한 분석: 생성된 조합별로 사용자들이 이모티콘을 구매하거나 서비스에 가입하는지 분석.
3. 최적의 결과 찾기: 최종적으로 가장 많은 서비스 가입자와 매출을 기록한 조합을 선택.

#include <bits/stdc++.h>
using namespace std;

/*
 * 1. 서비스 가입자를 최대로
 * 2. 판매액 최대로
 * n 명의 사용자들에게 m개의 이모티콘을 할인
 * 할인율은 10, 20, 30, 40 중 하나
 * 사용자들은 자신의 기준에 따라 {이모티콘 구매 가격 합} 이 일정 이상의 가격이 된다면
 *      -> 서비스 가입
 * 가입자를 최대로 늘리면서 판매액을 최대로 하였을때, {가입자 수, 매출액}
 */

int rate[] = {10,20,30,40};

vector<vector<int>> sales;

void dfs(int size, int cnt, int idx, vector<int> perm){
    if(cnt == size){
        sales.push_back(perm);
        return;
    }
    for(int i = 0; i<4; i++){
        perm[idx] += rate[i];
        dfs(size, cnt + 1, idx + 1, perm);
        perm[idx] -= rate[i];
    }
}

vector<int> highest(vector<vector<int>>& users, vector<int> emoticons){
    vector<int> ret(2,0);
    for(int i = 0; i<sales.size(); i++){

        vector<int> tmp = emoticons;
        vector<int> curRate = sales[i];

        for(int j = 0; j<sales[i].size(); j++){
            tmp[j] = (100 - sales[i][j]) * emoticons[j] / 100;
        }

        vector<int> cur(2,0);
        for(auto u : users){
            int buyRate = u[0];
            int serviceJoin = u[1];
            int curCost = 0;

            for(int k = 0; k<curRate.size(); k++){ 
                if(curRate[k] >= buyRate){
                    curCost += tmp[k];
                }
                if(curCost >= serviceJoin){
                    cur[0]++;
                    curCost = 0;
                    break;
                }
            }
            cur[1] += curCost;
        }

        if(ret[0] < cur[0]){
            ret = cur;
        }else if(ret[0] == cur[0] && ret[1] < cur[1]) ret = cur;
    }

    return ret;
}

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {

    vector<int> temp(emoticons.size(), 0);
    dfs(emoticons.size(), 0, 0, temp);

    vector<int> ans = highest(users, emoticons);

    return ans;
}