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

할인은 무조건 10%, 20%, 30%, 40% 만 가능하고 이모티콘은 최대 7개가 있으므로 각 이모티콘당 할인율을 완전탐색해도 O(4^7 ) 로 충분히 가능하다.

 

DFS를 사용해서 각 이모티콘마다 할인율이 설정됐으면 users 정보를 완전탐색해 구매기준에 따른 총 이모티콘 구매 가격을 계산한다.  (시간복잡도 O(4^7 * 100) 대략 160만)

 

문제 조건에 따라 현재 이모티콘 플러스보다 많이 사용할 경우 이모티콘 플러스 값을 갱신하고 price 값을 변환해준다.

 

 

#include <string>
#include <vector>
#include <iostream>
 
using namespace std;
 
int emo = 0;
int price = 0;
vector<int> vec;
int arr[4] = {10,20,30,40};
 
void dfs(vector<vector<int>> users, vector<int> emoticons) {                        
    if(vec.size() == emoticons.size()) {
        int emo_tmp = 0;
        int price_tmp = 0;
        
        for(int i=0; i<users.size(); i++) {
            int p = 0;
            
            for(int j=0; j<emoticons.size(); j++) {
                if(users[i][0] <= vec[j]) {
                    p = p + emoticons[j] * (100-vec[j]) / 100;
                }
            }
            
            if(p >= users[i][1]) { emo_tmp++; }
            else { price_tmp = price_tmp + p; }
        }
        
        if(emo < emo_tmp) {
            emo = emo_tmp;
            price = price_tmp;
        }
        else if(emo == emo_tmp && price < price_tmp) {
            price = price_tmp;
        }
        return;
    }
    
    for(int i=0; i<4; i++) {
        vec.push_back(arr[i]);
        dfs(users,emoticons);
        vec.pop_back();
    }
}
 
vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    vector<int> answer;
    
    dfs(users,emoticons);
    
    answer.push_back(emo);
    answer.push_back(price);
    
    return answer;
}