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

---

 

1. 4가지의 할인율을 가질 수 있으므로 n개의 이모티콘들의 할인율을 설정하는 방법의 수는 4^n이다.
2. 비트마스크를 사용하여 이모티콘들의 할인율을 설정하는 모든 방법을 탐색한다.
3. 서비스 가입자 수가 가장 많은 방법, 서비스 가입자 수가 같다면 판매 금액이 가장 높은 방법을 선택한다.

 

1. 4가지의 할인율을 가질 수 있으므로 n개의 이모티콘들의 할인율을 설정하는 방법의 수는 4^n이다.

 각 이모티콘별로 총 가지, 10%, 20%, 30%, 40% 중 하나의 할인율을 갖는다. 따라서 n개의 이모티콘들의 할인율을 설정하는 방법의 수는 4^n이다. 이모티콘의 개수 n은 최대 7로 매우 작기 때문에 모든 경우를 다 탐색하는 브루트포스를 사용하더라도 제한시간 내에 해결이 가능하다.

 

2. 비트마스크를 사용하여 이모티콘들의 할인율을 설정하는 모든 방법을 탐색한다.

 각 이모티콘들의 할인율은 비트마스크를 활용하여 나타내자. 4가지의 할인율을 모두 나타내기 위해서는 2비트가 필요(2^2=4)하다. 즉 이모티콘 1개당 2비트가 필요하므로, 총 2n개의 비트가 필요하다. 따라서 마스크의 범위는 [0, 2^n-1].

 

3. 서비스 가입자 수가 가장 많은 방법, 서비스 가입자 수가 같다면 판매 금액이 가장 높은 방법을 선택한다.

 이제 모든 경우(마스크)에 대해 전체 사용자의 구매 결과를 계산한다. 주어진 조건에 따르면 서비스 가입자 수를 늘리는 것이 우선이므로 답을 갱신할 때에는 서비스 가입자 수를 우선으로 비교하고, 그 다음 판매 금액을 비교하여 더 큰 값을 가지는 경우로 갱신하면 된다.

---

#include <string>
#include <vector>

using namespace std;

struct PayResult {
    int purchase_cost;  // 이모티콘 구매 비용
    int subscription;   // 이모티콘 플러스 서비스 가입 여부
    
    PayResult& operator+=(const PayResult& pr) {
        purchase_cost += pr.purchase_cost;
        subscription += pr.subscription;
        return *this;
    }
    
    bool operator<(PayResult& pr) const {
        // 플러스 서비스 가입자를 최대한 늘리는 것이 우선
        if (subscription != pr.subscription) return subscription < pr.subscription;
        return purchase_cost < pr.purchase_cost;
    }
};

struct User {
    int percentage; // 이모티콘 구매 기준 비율
    int threshold;  // 서비스가입 기준 가격
};

PayResult max(PayResult& lhs, PayResult& rhs) {
    return (lhs < rhs) ? rhs: lhs;
}

// 각 이모티콘의 할인율이 sales일 때 user의 구매 결과를 구하는 함수
PayResult calcPayResult(User user, vector<int>& emoticons, vector<int>& sales) {
    PayResult result = {0, 0};
    
    // 총 구매 금액 계산
    for (int i=0; i<emoticons.size(); i++) {
        if (sales[i] >= user.percentage) {
            result.purchase_cost += emoticons[i] * (100 - sales[i]) / 100;
        }
    }
    
    // threshold 이상인 경우 플러스 서비스 가입
    if (result.purchase_cost >= user.threshold) {
        result.purchase_cost = 0;
        result.subscription = 1;
    }
    
    return result;
}

// 각 이모티콘의 할인율이 sales일 때 전체 사용자의 구매 결과를 구하는 함수
PayResult calcTotalPayResult(vector<User>& users, vector<int>& emoticons, vector<int>& sales) {
    PayResult result = {0, 0};
    
    for (auto user: users) {
        result += calcPayResult(user, emoticons, sales);
    }
    
    return result;
}

// 비트마스크로 나타낸 n개의 이모티콘에 대한 할인율을 퍼센트로 변환하여 percentages 벡터에 담는 함수
void bitmaskToPercentage(int n, int mask, vector<int>& percentages) {
    percentages.resize(n, 0);
    
    for (int i=0; i<n; i++) {
        // 00=10%, 01=20%, 10=30%, 11=40%
        int submask = mask % 4; mask /= 4;
        percentages[i] = (submask + 1) * 10;
    }
}

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    vector<int> answer;
    
    // User 구조체 변환
    
    int un = users.size();
    vector<User> n_users(un);
    
    for (int i=0; i<un; i++) {
        n_users[i] = {users[i][0], users[i][1]};
    }
    
    
    // 브루트포스 - 각 이모티콘의 할인률을 설정하는 모든 경우의 수를 시도해보고 최댓값을 찾음
    
    int en = emoticons.size();
    PayResult max_result = {0, 0};
    vector<int> sales;
    
    // 4가지의 할인율을 가질 수 있으므로, 이모티콘 1개당 2비트 필요
    for (int mask = 0; mask < (1 << 2*en); mask++) {
        bitmaskToPercentage(en, mask, sales);
        PayResult temp_result = calcTotalPayResult(n_users, emoticons, sales);
        max_result = max(max_result, temp_result);
    }
    
    
    answer.push_back(max_result.subscription);
    answer.push_back(max_result.purchase_cost);
    
    return answer;
}