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

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

역시 사람은 잠을 잘 자고, 밥 먹고, 커피 한 잔 마시면서 진행해야 능률이 좋나 봅니다. 저번에 풀 땐 머리가 안 돌아가서 그냥 시간만 보내고 있었는데, 이번엔 카페에 와서 정상 컨디션으로 푸니까 금방 풀었네요.

 

판매하는 이모티콘의 최대 개수는 7개이고, 할인은 40%, 30%, 20%, 10% 이렇게 4가지 뿐이므로 최악일 때의 모든 경우의 수는 \( 4 ^ 7 = 16,384 \) 가지입니다. 유저의 최대 수가 100명이므로 \( 100 \times 7 \times 16,384 \) 번의 연산이 일어납니다. 이는 1억보다 작으므로 충분히 가능하겠네요.

 

그래서 저는 백트래킹(Backtracking)으로 모든 경우의 수를 검사하여, 문제에서 제시한 1. 가입자 수 최대, 2. 판매액 최대일 때 답을 갱신하는 형태로 코드를 작성하였습니다.

 

✏️소스 코드 및 결과

#include <string>
#include <vector>
using namespace std;
using User = vector<vector<int>>;
vector<int> discountRates = { 40, 30, 20, 10 };

struct Emoticon {
    Emoticon() { }
    Emoticon(int originalPrice, int discountRate) : _discountRate(discountRate) {
        _price = originalPrice * (1.0f - (static_cast<float>(discountRate) * 0.01f));
    }

    int _price;
    int _discountRate;
};

void Search(const User& users, const vector<int>& emoticons, vector<Emoticon>& discountedEmoticons, vector<int>& answers, int emoticonIdx) {
    if (discountedEmoticons.size() == emoticons.size()) {
        int totalBuyingPrice = 0;
        int member = 0;

        for (const auto& user : users) {
            int requireDiscountRate = user[0];
            int membershipStandardPrice = user[1];
            int buying = 0;

            for (const auto& emoticon : discountedEmoticons) {
                if (emoticon._discountRate < requireDiscountRate)
                    continue;

                buying += emoticon._price;

                if (buying >= membershipStandardPrice) {
                    member++;
                    break;
                }
            }

            totalBuyingPrice += (buying < membershipStandardPrice) ? buying : 0;
        }

        if (answers[0] == member and answers[1] < totalBuyingPrice)
            answers[1] = totalBuyingPrice;

        else if (answers[0] < member) {
            answers[0] = member;
            answers[1] = totalBuyingPrice;
        }

        return;
    }

    for (int ei = emoticonIdx; ei < emoticons.size(); ei++) {
        for (int di = 0; di < discountRates.size(); di++) {
            discountedEmoticons.emplace_back(Emoticon(emoticons[ei], discountRates[di]));
            Search(users, emoticons, discountedEmoticons, answers, ei + 1);
            discountedEmoticons.pop_back();
        }
    }
}

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    vector<int> answers { 0, 0 };
    vector<Emoticon> discountedEmoticons;
    
    Search(users, emoticons, discountedEmoticons, answers, 0);
    return answers;
}