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

할인율이 10, 20, 30, 40로 4가지 밖에 안되며

이모티콘 총 갯수의 상한선도 7개밖에 안된다

 

이는 모든 경우의 수를 탐색해도 4의 7승이므로 제한시간 내에 가능하다.

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> sales; // 세일
vector<pair<int, int>> answer;

// 할인률을 10, 20, 30, 40 까지 경우의 수
// 내림차순으로 해서, 첫 전환점까지 하면 될 것 같은데

// 40 40 40 40 40 40 40
// 10 10 10 10 10 10 10 ~ 40 40 40 40 40 40 40 모든 경우 수

void calculate(vector<vector<int>>& users, vector<int>& emoticons) {

    int totalSubscribe = 0;
    int totalPrice = 0;
    
    for(int i = 0; i < users.size(); i++) {
        
        int price = 0;

        
        for(int j = 0; j < emoticons.size(); j++) {
            if(users[i][0] <= sales[j]) {
                price += emoticons[j] - (emoticons[j] * sales[j] / 100);
            }
        }
        
        if(price >= users[i][1]) {
            totalSubscribe++; // 프리미엄 가입
        } else {
            totalPrice += price;
        }
    }
    
    answer.push_back({totalSubscribe, totalPrice});
}

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

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    
    dfs(users, emoticons);
    
    sort(answer.begin(), answer.end(), greater<>());
    
    return {answer[0].first, answer[0].second};

}

 

 

 

---

 

다시 풀었다. 잘 했따.

#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>
using namespace std;

/*
보고 든 생각. 이거 내가 어케 풀었지?
어떻게 접근해야 하는지 감이 안오는데.
감이 좀 많이 죽었나.

4의 7승 = 총 경우의 수

40 40 40 40
40 40 40 30
40 40 40 20
40 40 40 10

40 40 30 40
40 40 30 30
*/

int N;
int M;

int discount[8];
vector<pair<int, int>> v;

int cmp(pair<int, int>& a, pair<int, int>& b) {
    if(a.first != b.first) return a.first > b.first;
    if(a.second != b.second) return a.second > b.second;
}

void calculate(vector<vector<int>>& users, vector<int>& emoticons) {
    
    int totalMoney = 0;
    int totalPlus = 0;
    
    for(int i = 0; i < M; i++) {
        int money = 0;
        for(int j = 0; j < N; j++) {
            if(discount[j] >= users[i][0]) {
                money = (money + emoticons[j] - (emoticons[j] * discount[j] / 100));
            }
        }
        if(money >= users[i][1]) {
            totalPlus++;
        } else {
            totalMoney += money;
        }
    }
    
    v.push_back({totalPlus, totalMoney});
}

void dfs(int index, vector<vector<int>>& users, vector<int>& emoticons) {
    
    if(index == N) {
        calculate(users, emoticons);
        return;
    }
    
    for(int i = 10; i <= 40; i+=10) {
        discount[index] = i;
        dfs(index + 1, users, emoticons);
    }
}

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    
    ::N = emoticons.size();
    ::M = users.size();
    
    dfs(0, users, emoticons);
    
    sort(v.begin(), v.end(), cmp);
    
    
    return {v[0].first, v[0].second};
}