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

프로그래머스

 

📄 문제

카카오톡에서는 이모티콘을 무제한으로 사용할 수 있는 이모티콘 플러스 서비스 가입자 수를 늘리려고 합니다.
이를 위해 카카오톡에서는 이모티콘 할인 행사를 하는데, 목표는 다음과 같습니다.

이모티콘 플러스 서비스 가입자를 최대한 늘리는 것.
이모티콘 판매액을 최대한 늘리는 것.
1번 목표가 우선이며, 2번 목표가 그 다음입니다.

이모티콘 할인 행사는 다음과 같은 방식으로 진행됩니다.

n명의 카카오톡 사용자들에게 이모티콘 m개를 할인하여 판매합니다.
이모티콘마다 할인율은 다를 수 있으며, 할인율은 10%, 20%, 30%, 40% 중 하나로 설정됩니다.
카카오톡 사용자들은 다음과 같은 기준을 따라 이모티콘을 사거나, 이모티콘 플러스 서비스에 가입합니다.

각 사용자들은 자신의 기준에 따라 일정 비율 이상 할인하는 이모티콘을 모두 구매합니다.
각 사용자들은 자신의 기준에 따라 이모티콘 구매 비용의 합이 일정 가격 이상이 된다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입합니다.

 

📝 풀이

#include <string>
#include <vector>
using namespace std;

int sale[]{10, 20, 30, 40};

vector<int> ch;
vector<int> answer{ -1, -1 };

void DFS(vector<vector<int>> users, vector<int> emoticons, int l)
{
    if(l == emoticons.size())
    {
        int reg = 0;
        int earn = 0;
        
        for(int i = 0; i < users.size(); ++i)
        {
            int price = 0;
            for(int j = 0; j < ch.size(); ++j)
                if(users[i][0] <= sale[ch[j]]) // 할인율 이상인경우?
                    price += (int)(emoticons[j] / 100.0f * (100 - sale[ch[j]])); // 구매
            
            // 구매 가격이 user의 가격 이상이라면?
            if(price >= users[i][1]) ++reg; // 이모티콘 플러스 가입
            else earn += price; // 수익 더하기
        }
        
        if(answer[0] <= reg)
        {
            if(answer[0] < reg)
                answer[1] = 0;
            
            answer = max(answer, {reg, earn});
        }
    }
    else
    {
        for(int i = 0; i < 4; ++i)
        {
            ch[l] = i;
            DFS(users, emoticons, l + 1);
        }
    }
}


vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    
    ch = vector<int>(emoticons.size());
    
    DFS(users, emoticons, 0);
    
    return answer;
}

• 재귀함수를 이용하여 emoticons에서 가능한 모든 할인의 조합을 구하였습니다.
• 해당 할인 비율이 사용자가 무조건 구매하는 할인율이라면, price에 누적하여 더합니다.
• 모든 이모티콘을 검사하였다면, 사용자의 최대 비용 이상인지 검사하여 이모티콘 플러스 가입 여부를 확인합니다.
• 이모티콘 플러스를 가입하지 않는다면, earn에 price를 더하여 조건에 맞는 이모티콘 플러스 가입자 수와, 나머지 수익이 가장 높은 정답을 비교하여 갱신합니다.