[C++] 프로그래머스 이모티콘 할인행사

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

프로그래머스

풀이

할인율 변수 범위 4, 이모티콘 변수 범위 7 이기 때문에, 모든 할인율에 대해 검사하는 O(4^7)으로 DFS를 돌려도 괜찮겠다고 생각했다.

1. discountRate 벡터 길이가 이모티콘 수와 같아지면, 모든 유저에 대해 이모티콘 총액 계산을 진행한다.

2. 한도 이상 쓴 경우 serviceUser++, tmpMoney=0 처리 후 break한다.

3. 모든 유저에 대해 계산이 끝나면, 문제 기준에 맞게 답을 업데이트 한다. (가입 유저 > 판매액 순)

#include <string>
#include <vector>

using namespace std;
// 가입자 > 판매액
int dr[4]={10, 20, 30, 40};
int ans1, ans2;

void dfs(vector<int> discountRate, vector<vector<int>> users, vector<int> emoticons){
    if (discountRate.size()==emoticons.size()){
        int serviceUser=0;
        int salesMoney=0;
        for (int i=0; i<users.size(); i++){
            int userDiscountRate = users[i][0];
            int maxMoney = users[i][1];
            int tmpMoney=0;
            // 이모티콘 구매 진행
            for (int j=0; j<emoticons.size(); j++){
                int dcr = discountRate[j];
                // 구매가능
                if (dcr >= userDiscountRate){
                    int newPrice = emoticons[j]*(100-dcr)/100;
                    tmpMoney+= newPrice;
                }
                // 한도 이상 쓴 경우, 유저 추가
                if (tmpMoney>=maxMoney){
                    tmpMoney=0;
                    serviceUser++;
                    break;
                }
            }
            // 유저 한명에 대한 판매액 업데이트
            salesMoney+=tmpMoney;
        }
        // 유저 우선
        if (serviceUser>ans1){
            ans1=serviceUser;
            ans2=salesMoney;
        }
        // 유저 수 같을 경우 판매액 우선
        else if (serviceUser==ans1){
            if (salesMoney > ans2){
                ans2 = salesMoney;
            }
        }
    }
    else{
        for (int i=0; i<4; i++){
            discountRate.push_back(dr[i]);
            dfs(discountRate, users, emoticons);
            discountRate.pop_back();
        }
    }
};

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    vector<int> answer;
    vector<int> dcRate;
    dfs(dcRate, users, emoticons);
    answer.push_back(ans1);
    answer.push_back(ans2);
    return answer;
}