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

문제 설명

카카오톡 사용자 n명의 구매 기준을 담은 2차원 정수 배열 users, 이모티콘 m개의 정가를 담은 1차원 정수 배열 emoticons가 주어집니다. 이때, 행사 목적을 최대한으로 달성했을 때의 이모티콘 플러스 서비스 가입 수와 이모티콘 매출액을 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한 사항

• 1 ≤ users의 길이 = n ≤ 100
  • users의 원소는 [비율, 가격]의 형태입니다.
  • users[i]는 i+1번 고객의 구매 기준을 의미합니다.
  • 비율% 이상의 할인이 있는 이모티콘을 모두 구매한다는 의미입니다.
    • 1 ≤ 비율 ≤ 40
  • 가격이상의 돈을 이모티콘 구매에 사용한다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입한다는 의미입니다.
    • 100 ≤ 가격 ≤ 1,000,000
    • 가격은 100의 배수입니다.
• 1 ≤ emoticons의 길이 = m ≤ 7
  • emoticons[i]는 i+1번 이모티콘의 정가를 의미합니다.
  • 100 ≤ emoticons의 원소 ≤ 1,000,000
  • emoticons의 원소는 100의 배수입니다.

입출력 예

users	emoticons	result
[[40, 10000], [25, 10000]]	[7000, 9000]	[1, 5400]
[[40, 2900], [23, 10000], [11, 5200], [5, 5900], [40, 3100], [27, 9200], [32, 6900]]	[1300, 1500, 1600, 4900]	[4, 13860]

풀이

backtracking 알고리즘을 사용하여 푸는 문제입니다.

백트래킹이란 가지치기를 통해 가지 않아도 되는 루트는 고려하지 않고 탐색하는 완전 탐색 기법입니니다.

즉, DFS를 사용하여 조건에 맞지 않으면 중단하고 이전으로 되돌아가 다시 조건에 맞는 해를 찾아가는 기법입니다. 

#include <string>
#include <vector>

using namespace std;

int maxSales = 0, maxEmoticonPlus = 0;

void calculate(const vector<int>& salesRates, const vector<vector<int>>& users, const vector<int>& emoticons){
    
    int emoticonPlus = 0, sales = 0;
    for(const auto& it : users){
        int tmp = 0;
        for(int i = 0; i < salesRates.size(); i++){
            if( it[0] > salesRates[i]){
                continue;
            }
            tmp += (emoticons[i] / 100) * (100 - salesRates[i]);
        }
        if(tmp >= it[1]){
            emoticonPlus++;
        }
        else{
            sales += tmp;
        }
    }
    
    if(maxEmoticonPlus > emoticonPlus){
        return;
    }
    if(maxEmoticonPlus == emoticonPlus && maxSales >= sales){
        return;
    }
    maxEmoticonPlus = emoticonPlus;
    maxSales = sales;

}

void dfs(vector<int>& salesRates, vector<vector<int>>& users, vector<int>& emoticons){
    if(salesRates.size() == emoticons.size()){
        calculate(salesRates, users, emoticons);
        return;
    }
    for(int i = 10; i <= 40; i += 10){
        salesRates.push_back(i);
        dfs(salesRates, users, emoticons);
        salesRates.pop_back();
    }
}

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {

    vector<int> salesRates;
    dfs(salesRates, users, emoticons);
    
    vector<int> answer;
    answer.push_back(maxEmoticonPlus);
    answer.push_back(maxSales);
    return answer;
}

 

다른 풀이

#include <string>
#include <vector>

using namespace std;

vector<int> answer(2, 0);
int salesRates[8];

void dfs(int pos, const vector<vector<int>>& users, const vector<int>& emoticons){
    
    if(pos == emoticons.size()){
        int total_price = 0, total_user = 0;
        for(const auto& it : users){
            int tmp = 0;
            for(int j = 0; j < emoticons.size(); j++){
                if(salesRates[j] >= it[0]){
                    tmp += emoticons[j] * (100 - salesRates[j]) / 100;
                }
            }
            if(tmp >= it[1]){
                total_user++;
            }
            else{
                total_price += tmp;
            }
        }
        answer  = max(answer , {total_user, total_price});
        return;
    }
    for(int i = 1; i <= 4; i++){
        salesRates[pos] = i * 10;
        dfs(pos + 1, users, emoticons);
    }
}

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