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

프로그래머스

 

• 일단 dfs를 통해 각 이모티콘들의 할인 조합을 만들어주기로 함
• 할인율 4종류에 이모티콘은 최대 7종류라 dfs 자체는 최대 28번 수행이라 시간 초과는 없을거라 예상
• 이후 조합이 다 만들어지면 매출액과 플러스 가입자 수를 구함
• 조건 중 플러스 가입자 수 증가가 1순위, 매출액 최대화가 2순위이므로 플러스 가입자 수가 더 많은 조합의 가입자 수와 매출액을 저장하고 가입자 수가 동일하다면 매출액을 비교해서 저장

 

나름 간단한 완전탐색 문제였다.

#include <string>
#include <vector>

using namespace std;

// 할인율 배열
int discount[4] = {10, 20, 30, 40};

void dfs(int cnt, int size, vector<vector<int>> users, vector<int> emoticons, 
         vector<int>& answer, vector<pair<int, int>>& prices) {
    // 모든 이모티콘에 할인 적용이 완료되었을 때
    if(cnt == size) {
        // 플러스 가입자 수, 매출액
        int plus = 0, total = 0;
        
        // 각 사용자마다
        for(int i = 0;i < users.size(); i++)
        {
            int tmp = 0;
            
            for(int j = 0;j < size; j++)
                // 할인율이 마음에 들면
                if (users[i][0] <= prices[j].second) tmp += prices[j].first;
            // 소지금보다 구매에 많이 사용한다면 플러스 이용자
            if(tmp >= users[i][1]) plus++;
            else total += tmp;
        }
        
        // 가입자 수가 더 많을 때 << 1번 목표
        if (plus > answer[0])
        {
            answer[0] = plus;
            answer[1] = total;
        }
        // 가입자 수가 동일하다면 판매액이 더 클 때 << 2번 목표
        else if(plus == answer[0] && total >= answer[1]) answer[1] = total;
        
        return ;
    }
    
    // 이모티콘 할인 조합 만들기
    for(int i = 0; i < 4; i++) {
        prices[cnt].first = emoticons[cnt] * (100 - discount[i]) / 100;
        prices[cnt].second = discount[i];
        dfs(cnt + 1, size, users, emoticons, answer, prices);
    }
}

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    vector<int> answer(2, 0);
    // {할인가, 할인율} 쌍
    vector<pair<int, int>> prices(7, {0, 0});
    
    dfs(0, emoticons.size(), users, emoticons, answer, prices);
    
    return answer;
}