이모티콘 할인행사 [Lv.2]

프로그래머스

 

이모티콘을 (10, 20, 30, 40%)할인 하여 판매할 때 사람들은 자신이 원하는 할인율이면 무조건 구매합니다.

하지만 총 구매 금액이 "이 돈이면 이모티콘 플러스 가입하지;;"라고 한다면 구매를 취소하고 이모티콘 플러스에 가입하게 됩니다.

 

이때 이모티콘별 할인율을 조정하여 얻을 수 있는

이모티콘 플러스 가입자수 최대 가입자 수와 최대 판매금액을 출력하는 문제입니다.

- 가입자수가 판매금액보다 우선순위가 높음 (가입자수 1000명, 판매금액 0원 > 가입자수 999명, 판매금액 1200억)

 

풀이방법

풀이 방법은 생각보다 간단합니다.

1. 이모티콘 * 할인율의 모든 경우의 수를 만들어 놓기

2. 모든 경우의 수에서 이모티콘을 판매할 때 발생하는 가입자 수와, 판매금액을 기록

3. 기록된 가입자 수, 판매 금액에서 최대값 추출

4. 출력

 

저는 모든 경우의 수를 만드는 과정에서 DFS를 사용했습니다.

void dfs(vector<vector<int>>& users, vector<int>& emoticons) {                     
    if (_rates.size() < emoticons.size())
    {
        for (int i = 10; i <= 40; i += 10)
        {
            _rates.push_back(i);
            dfs(users, emoticons);
            _rates.pop_back(); // rate vector 재사용을 위한 pop
        }
        return;
    }
    ...
    ...
    ...

이모티콘이 2개라면 

[10, 10], [10, 20], [10, 30], [10, 40], 
[20, 10], [20, 20], [20, 30], [20, 40], 
[30, 10], [30, 20], [30, 30], [30, 40], 
[40, 10], [40, 20], [40, 30], [40, 40]

위와 같은 경우의 수가 만들어집니다. [첫번째 이모티콘 할인율, 두번째 이모티콘 할인율]

 

   // kep -> kakao emoticon plus의 약자
    int tmp_Kep = 0;
    int tmp_price = 0;

    for (int i = 0; i < users.size(); i++)
    {
        int p = 0;
        for (int j = 0; j < emoticons.size(); j++)
        {
            if (users[i][0] > _rates[j])
                continue;

            p += emoticons[j] * ((100 - _rates[j]) / 100.0f);     
        }

        // i번 유저가 총 구매할 비용
        if (p >= users[i][1])
            tmp_Kep++;
        else
            tmp_price += p;
    }

이후 해당 경우의 수 에서의 "모든 유저의 구매 현황을 기록"하였습니다.

 

if (tmp_Kep > _kep)
{
    _kep = tmp_Kep;
    _price = tmp_price;
}
else if(tmp_Kep == _kep && tmp_price > _price)
{
    _price = tmp_price;
}

 

현재 경우의 수에서 이모티콘 플러스 가입자 수가 더 많다면 변수 값을 덮어씌어주었습니다.

 

정답 코드

#include <string>
#include <vector>
#include <iostream>
 
using namespace std;
 
int _kep = 0;
int _price = 0;
vector<int> _rates;
 
void dfs(vector<vector<int>>& users, vector<int>& emoticons) {                     
    if (_rates.size() < emoticons.size())
    {
        for (int i = 10; i <= 40; i += 10)
        {
            _rates.push_back(i);
            dfs(users, emoticons);
            _rates.pop_back(); // rate vector 재사용을 위한 pop
        }
        return;
    }

    int tmp_Kep = 0;
    int tmp_price = 0;

    for (int i = 0; i < users.size(); i++)
    {
        int p = 0;
        for (int j = 0; j < emoticons.size(); j++)
        {
            if (users[i][0] > _rates[j])
                continue;

            p += emoticons[j] * ((100 - _rates[j]) / 100.0f);     
        }

        // i번 유저가 총 구매할 비용
        if (p >= users[i][1])
            tmp_Kep++;
        else
            tmp_price += p;
    }

    if (tmp_Kep > _kep)
    {
        _kep = tmp_Kep;
        _price = tmp_price;
    }
    else if(tmp_Kep == _kep && tmp_price > _price)
    {
        _price = tmp_price;
    }
    
}
 
vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    dfs(users, emoticons);
    return {_kep, _price};
}