[프로그래머스 2레벨] 이모티콘 할인행사 (C++)

#include <string>
#include <vector>

using namespace std;

int arr[4] = {10, 20, 30, 40};
vector<int>v;
int sign, price; //가입자 및 금액

void dfs(vector<vector<int>> users, vector<int> emoticons)
{
    if(v.size()==emoticons.size()) //할인율 모두 결정
    {
        int tmp_sign = 0;
        int tmp_price = 0;
        for(int i=0; i<users.size(); i++)
        {
            int tmp = 0;
            for(int j=0; j<emoticons.size(); j++)
            {
                if(users[i][0] <= v[j]) tmp += emoticons[j] * (100-v[j]) / 100; //할인률 비교후 구매
            }
            
            if(tmp >= users[i][1]) tmp_sign++; //구매 금액이 일정량 이상이면 이모티콘 가입
            else tmp_price+=tmp; //아니면 매출액에 저장
        }
        
        if (tmp_sign > sign || (tmp_sign == sign && tmp_price > price)) //가입자수 최대 또는 가입자수가 같지만 금액 최대
        {
            sign = tmp_sign;
            price = tmp_price;
        }
        return;
    }
    
    for(int i=0; i<4; i++) //할인률 조합 
    {
        v.push_back(arr[i]);
        dfs(users, emoticons);
        v.pop_back();
    }
}
vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    vector<int> answer;
    
    dfs(users, emoticons);
    answer.push_back(sign);
    answer.push_back(price);
    return answer;
}

 

할인률 조합에 대한 모든 경우 탐색을 위해 dfs를 이용한다.

정해진 할인률은 {10, 20, 30, 40}이다.

 

이제 dfs 통해 할인률을 모두 결정했을 때 계산을 시작한다.

모든 유저에 대해서 체크하며, 현재 유저의 가능 할인률보다 할인률이 크다면 할인된 금액만큼 구매한다.

이후 이렇게 구한 금액에 대해 해당 유저의 임계금액을 넘기면 이모티콘을 가입하고, 아니면 매출액에 저장한다.

 

우리는 가입자 수를 최대로 해야하기 때문에 이에 맞게 조건문을 세워 체크해야한다.

전역변수를 통해 최대 가입 자 수를 체크하며 갱신해주고, 가입자수가 같지만 금액이 다른 경우를 생각하여 금액 또한 전역변수로 선언하여 최대 금액을 갱신할 수 있도록 해준다.