[C++]프로그래머스 - 이모티콘 할인행사(조합)

난이도 : Lv2 (중)

풀이 시간 : 35분

알고리즘 유형 : 조합, DFS

풀이 방법 : 가능한 경우 탐색 후 조합 

 

문제 설명

카카오톡은 이모티콘 플러스 서비스 가입자를 늘리기 위해 할인 행사를 진행합니다.
목표는 이모티콘 플러스 서비스 가입자 수를 최대화하고, 그 다음으로 이모티콘 판매액을 늘리는 것입니다.

 

• n명의 사용자에게 m개의 이모티콘을 할인해서 판매한다.
• 이모티콘마다 할인율은 10%, 20%, 30%, 40% 중 하나이다.
• 사용자는 자신이 설정한 할인율 이상으로 할인이 되는 이모티콘을 구매하고,
  구매 금액이 설정 금액 이상이면 플러스 서비스에 가입한다.

예시

사용자할인율한도

1번	40%	10,000원
2번	25%	10,000원

이모티콘가격

1번	7,000원
2번	9,000원

이모티콘을 40% 할인하면, 두 사용자는 모두 이모티콘을 구매하지만 플러스 서비스 가입자는 없습니다.

하지만 할인율을 다르게 적용하면, 1번 이모티콘은 30%, 2번 이모티콘은 40% 할인 시
2번 사용자는 플러스 서비스에 가입하고, 1번은 계속 구매하게 됩니다.

해결 방법

모든 할인율 조합을 시도하면서 가입자 수와 매출액을 최대로 만들 수 있는 방법을 찾으면 끝입니다.

DFS 를 활용하여 모든 조합을 확인했습니다.

 

 

아래는 코드입니다.

#include <string>
#include <vector>

using namespace std;

float discount_f[4] = { 0.9f, 0.8f, 0.7f, 0.6f };
int discount_i[4] = { 10, 20, 30, 40 };
int emoPlus = -1;
int emoPurchase = -1;


void dfs(int cur, const vector<vector<int>>& users, const vector<int>& emoticons, vector<pair<int, int>>& answer)
{
    if (emoticons.size() == answer.size())
    {
        int plus = 0;
        int purchase = 0;

        // 모두 순회
        // users[0] 이상 할인 하는 품목을 사자
        // 10,000 이 넘는다면 이모 플러스로
        for (int i = 0; i < users.size(); ++i)
        {
            int sum = 0;
            for (int j = 0; j < answer.size(); ++j)
            {
                if (users[i][0] <= answer[j].first)
                {
                    sum += answer[j].second;
                }
            }

            if (sum >= users[i][1])
                ++plus;
            else
                purchase += sum;

        }

        if (emoPlus < plus || (emoPlus == plus && emoPurchase < purchase))
        {
            emoPlus = plus;
            emoPurchase = purchase;
        }

        return;
    }

    for (int i = cur; i < emoticons.size(); ++i)
    {
        for (int j = 0; j < 4; ++j)
        {
            answer.push_back({ discount_i[j], (float)emoticons[i] * discount_f[j] });
            dfs(i + 1, users, emoticons, answer);
            answer.pop_back();
        }
    }
}

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) 
{
    vector<pair<int, int>> answer;
    dfs(0, users, emoticons, answer);

    return vector<int>{emoPlus, emoPurchase};
}