[프로그래머스] 이모티콘 할인행사 c++ / 2023 KAKAO BLIND RECRUITMENT (중복 조합 dfs)

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/150368

프로그래머스

---

풀이

카카오톡의 이모티콘 목표 조건

1. 이모티콘 플러스 서비스 가입자를 최대한 늘리는 것.
2. 이모티콘 판매액을 최대한 늘리는 것.

을 최대한으로 달성했을때 이모티콘 플러스 서비스 가입자수, 이모티콘 매출액을 구하는 문제이다.

 

처음 문제를 보고 완전탐색 말고 다른 방법을 고민했는데, 우선 완전탐색으로 정답 확인을 받았다.

 

이 문제의 큰 힌트는 아래부분이다.

• 이모티콘마다 할인율은 다를 수 있으며, 할인율은 10%, 20%, 30%, 40% 중 하나로 설정됩니다.

즉 할인율이 넷 중 하나로 고정된다는 것이다. 따라서 dfs로 이모티콘 별 할인 조합을 구해야 한다.

따라서 아래와 같은 프로세스로 백트래킹 방식으로 풀이하면 될 것 같다.

1. dfs로 이모티콘 별 할인율을 구한다. (중복 조합)
2. 구한 경우, 플러스 서비스 가입자수 & 매출액을 구해 더 좋은 조건이면 정답을 갱신한다.

중복조합은 아래 코드를 참고하면 된다.

int discount[4] = {10, 20, 30, 40};

void dfs(vector<int> sale, vector<vector<int>> users, vector<int> emoticons){
    if(sale.size() == emoticons.size()){
        calculate(sale, users, emoticons);
        return; 
    }
    for(int i = 0; i < 4; i++){
        sale.push_back(discount[i]);
        dfs(sale, users, emoticons);
        sale.pop_back();
    }
}

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    vector<int> sale;
    dfs(sale, users, emoticons); // 모든 할인 중복조합
    return ans;
}

---

코드

#include <string>
#include <vector>

using namespace std;

int discount[4] = {10, 20, 30, 40};
vector<int> ans(2, 0);

void calculate(vector<int> sale, vector<vector<int>> users, vector<int> emoticons){
    int plus = 0, sum = 0;
    vector<int> buyPrice(users.size(), 0); // 구매 가격
    vector<bool> check(users.size(), false); // plus 가입자인지 체크
    for(int i = 0; i < emoticons.size(); i++){
        int salePrice = (emoticons[i] * (100 - sale[i])) / 100; // 할인 임티 가격
        for(int j = 0; j < users.size(); j++){
            if(check[j]) continue; // 플러스 가입자면 계산안하고 패스
            // 기준 넘으면 구매
            if(sale[i] >= users[j][0]){
                buyPrice[j] += salePrice;
                // 가격 기준 넘으면 플러스 가입
                if(buyPrice[j] >= users[j][1]){
                    plus++;
                    buyPrice[j] = 0;
                    check[j] = true;
                }
            }
        }
    }
    for(auto elem : buyPrice)
        sum += elem;
    if(plus > ans[0] || (plus == ans[0] && sum > ans[1])){
        ans[0] = plus;
        ans[1] = sum;
    }
}

void dfs(vector<int> sale, vector<vector<int>> users, vector<int> emoticons){
    if(sale.size() == emoticons.size()){
        calculate(sale, users, emoticons);
        return; 
    }
    for(int i = 0; i < 4; i++){
        sale.push_back(discount[i]);
        dfs(sale, users, emoticons);
        sale.pop_back();
    }
}

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    vector<int> sale;
    dfs(sale, users, emoticons); // 모든 할인 중복조합
    return ans;
}