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

문제

문제 길이가 길어 문제는 링크로 확인 부탁드립니다.

 

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

프로그래머스

 

---

문제 풀이

해당 문제는 조건에 부합하는 최적의 이모티콘 각 할인률을 구하는 문제이다. 

 

문제에서 중요한 조건은 아래와 같다.

 

1. 1번 목표가 우선이며, 2번 목표가 그 다음입니다.

2. 1 ≤ emoticons의 길이 = m ≤ 7 , 할인율은 10%, 20%, 30%, 40% 중 하나로 설정

 

1번 조건은 이모티콘 판매 가격이 아무리 높더라도 이모티콘 플러스 가입자가 많은 케이스를 선택해야 한다는 조건이다

 

2번 조건에 의하면 완전 탐색을 할 경우 4^7의 경우의 수가 나오므로 시간 초과 우려가 없다는 것이다.

 

그렇기에 완전 탐색으로 문제를 풀었다.

 

우선 DFS로 이모티콘 할인률의 모든 케이스를 구하고, 이를 단순 계산하여 답을 구하면 된다.

 

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

int emoticonSize;
vector<int> discount = {10,20,30,40};
vector<vector<int>> discountCase = {};

void DFS (vector<int> p){
    if(p.size() == emoticonSize){
        discountCase.push_back(p);
        return;
    }
    for(int rate : discount){
        p.push_back(rate);
        DFS(p);
        p.pop_back();
    }
}


vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    vector<int> answer = {0,0};
    emoticonSize = emoticons.size();
    
    DFS({});
    for(vector<int> discountRate : discountCase){
        int plusCount = 0;
        int sales = 0;
        
        for(vector<int> user : users){
            
            int minDiscount = user[0];
            int plusLine = user[1];
            int buy = 0;
        
            for(int i = 0; i < emoticonSize; i++){
                if(discountRate[i] < minDiscount)   continue;
                buy += emoticons[i] * (100 - discountRate[i]) / 100;
            }
            
            
            
            if(buy >= plusLine){
                plusCount++;
            }else{
                sales += buy;
            }
        }
        if(answer[0] < plusCount){
            answer[0] = plusCount;
            answer[1] = sales;
        }else{
            if(answer[0] == plusCount && answer[1] < sales){
                answer[1] = sales;
            }
        }
    }
    
    
    return answer;
}