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

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

 

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

프로그래머스

---

 

 

해결전략

 

구현

깊이우선탐색 DFS

 

---

 

정답코드

 

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

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

vector<pair<int, int>> price(7); // 이모티콘 가격, 할인율

void DFS(int idx, const vector<vector<int>>& users, const vector<int>& emo)
{
    if(idx == m)
    {
        int ppl = 0, sumPrice = 0; // ppl: 구독자 수, sumPrice: 이모티콘들을 구매해서 지불해야할 비용
        for(int i = 0; i < n; i++)
        {
            int temp = 0; // 이모티콘 구매비용
	        for(int j = 0; j < m; j++){
		        if(users[i][0] <= price[j].second){ // 할인율을 만족해 이모티콘을 구입하는 경우
                    temp += price[j].first; // 구매비용 누적
		        }
	        }

            if(temp >= users[i][1]){ // 구매비용이 사용자가 준비한 금액보다 많은 경우 구독
                ppl++;
            }
            else{ 
                sumPrice += temp; 
            }
        }

        if(answer[0] < ppl){ // 가입자 수가 더 많은 경우 갱신 
            answer[0] = ppl;
            answer[1] = sumPrice;
        }
        else if (answer[0] == ppl && answer[1] <= sumPrice) { // 가입자 수는 같지만 구매비용이 더 많은 경우
            answer[1] = sumPrice;
        }

        return;
    }
	
    for (int i = 0; i < 4; i++)
    {
        price[idx].first = (100 - discount[i]) * emo[idx] / 100; // 할인된 이모티콘 가격
        price[idx].second = discount[i]; // 할인율
        DFS(idx + 1, users, emo);
    }
}

vector<int> solution(vector<vector<int>> users, vector<int> emo) {
    n = users.size();
    m = emo.size();

    DFS(0, users, emo);

    return answer;
}

int main(){
    vector<vector<int>> test1 = { {40, 10000}, {25, 10000} };
    vector<vector<int>> test2 = { {40, 2900},{23, 10000},{11, 5200},{5, 5900},{40, 3100},{27, 9200},{32, 6900 }};
    vector<int> testcase1 = { 7000, 9000 };
    vector<int> testcase2 = { 1300, 1500, 1600, 4900 };

    solution(test1, testcase1);
    solution(test2, testcase2);

    return 0;
}

 

 

---