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

https://school.programmers.co.kr/learn/courses/30/lessons/150368

프로그래머스

---

문제풀이

완전 탐색을 할 수 있는지시간 복잡도를 먼저 계산해 보았다.

할인율의 종류가 4가지이고, 최대 이모티콘 개수가 7개이므로 4^7이 나온다. 거기에 사람 n은 최대 100이다. 이모티콘 할인 모든 경우에 수에 따라 사람마다 각각 이모티콘을 살지, 이모티콘 플러스를 살지 계산해 주어야 하므로 4^7 X 100 이다. 계산하면 1,638,400이 나온다. 이정도면 충분히 완전탐색을 돌려도 된다.

dfs로 각 이모티콘의 할인율을 지정해 준뒤, 각 사람이 이모티콘을 구매하는지, 이모티콘 플러스를 구매하는지 계산해주면 된다.

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> answer(2);
int discount[] = {10, 20, 30, 40};
int emo_price[7];
int emo_count[7];
int joined;
int price;

void dfs(int idx, int n, vector<vector<int>>& users, vector<int>& emoticons) {
    if(idx == n) {
        int now_joined = 0;
        int now_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] <= emo_count[j]) {
                    p += emo_price[j];
                }
            }
            // 만약 유저별 제한 이상이면 이모티콘 플러스 구매
            if(p >= users[i][1]) now_joined++;
            else now_price += p;
        }
        
        // 이모티콘 플러스 유저 최댓값 찾기
        if(answer[0] < now_joined) {
            answer[0] = now_joined;
            answer[1] = now_price;
        }
        
        // 유저수 같을 때 금액 최댓값 찾기
        if(answer[0] == now_joined && answer[1] < now_price) {
            answer[1] = now_price;
        }
        
        return;
    }
    
    for(int i=0; i<4; i++) {
        emo_count[idx] = discount[i];
        emo_price[idx] = emoticons[idx]*(100-emo_count[idx])/100;
        dfs(idx+1, n, users, emoticons);
    }
}

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