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

문제 출처

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

프로그래머스

---

 

🔎문제 해석

1. 문제에서 목표는 2가지 있습니다.
   1. 이모티콘 플러스 서비스 가입자를 최대로 하는 것
   2. 이모티콘 판매액을 최대한 늘리는 것.
      • 여기서 1번 목표를 최우선시로 하고, 그다음 목표가 2번입니다.
2. 이모티콘의 할인률은 정해져 있습니다.
   1. 10%, 20% , 30%,  40%
   2. 각 이모티콘의 할인율을 조정해서, 우리는 최대한 많은 서비스 가입자를 모아야 합니다.
      판매금액도 최대로 해야 하구요
3. 고객은 2가지의 조건을 가지고 있습니다.
   1. 첫 번째 조건은 비율인데 , 해당 비율보다 낮은 할인율의 이모티콘은 구매하지 않습니다.
      1. 예를 들어서 1번 고객에 비율이 40%면 40%보다 낮게 할인하는 이모티콘은 구매하지 않습니다.
   2. 두 번째 조건은 가격인데, 이모티콘 구매 비용이 해당 가격보다 높아진다면, 그때는 모든 이모티콘의 구매를 철회하고, 이모티콘 플러스를 가입합니다

이모티콘의 각각의 할인율의 조합을 적용해서 최적의 해답을 찾아야 합니다!

 

이번 문제는 각 이모티콘의 개수 * 비율의 개수(10,20,30,40)의 조합으로 풀 수 있는 문제입니다.
각 이모티콘별로 할인률을 정해두고, 계속해서 할인률은 바꿔주는 형식으로 했습니다.

 

💻상세 코드

이모티콘의 할인율을 적용하는 함수입니다.

void sales(vector<int>sale,vector<vector<int>>users,vector<int>emoticons){

    if(sale.size()==emoticons.size()){
        funct(sale,users,emoticons);
        
        return;
    }
    for(int i=10; i<=40; i+=10){ //비율은 10%씩 증가함.
        sale.push_back(i);
        sales(sale,users,emoticons); //10, 20 , 30 , 40으로 돌린다.
        sale.pop_back();
    }
}

10,10,10,10으로 세팅한 뒤 함수를 빠져나온 뒤 10,10,10,20 ~~~~ 이렇게 모든 조합의 경우의 수를 검사합니다.

(이모티콘이 4개라면 10,10,10,10 -> 40,40,40,40까지 모든 경우의 수를 검사합니다)

 

이모티콘을 구매하고, 플러스 가입자를 결정하는 함수입니다.

void funct(vector<int>sale,vector<vector<int>> users, vector<int> emoticons){
    
    int emotPlus= 0;
    int total =0;
    for(int i=0; i<users.size();i++){
        int s=0;    
        for(int j=0; j<sale.size(); j++){

            if(users[i][0]>sale[j]){ //유저 할인률보다 낮으면 사질 못함
                continue;
            }
            s+= (emoticons[j]/100) *( 100-sale[j]);  //이모티콘 가격의 할인비율을 적용해서 더해줌.        
        }
        if(s>=users[i][1]){ //상한 금액을 넘는다면
            emotPlus++;
        }
        else{ //상한 금액을 안넘는다면
            total+=s; //금액을 더해줌.
        }
    }
    if(maxPlus>emotPlus){ //만약 가입자수가 적다면 되돌아감
        return ;
    }
    else if(maxPlus ==emotPlus && maxCost > total){ //이모티콘 플러스 가입자수가 같은데 코스트가 더 낮다면 되돌아감.
        return;
    }
    //위 조건에 해당하지 않는다면 값을 최신화해줌.
    maxCost=total;
    maxPlus = emotPlus;        
}

• 할인률이 유저가 정해놓은 할인률보다 낮다면 이모티콘은 구매하지 못합니다.
• 만약 높다면 그때의 할인율에 해당하는 이모티콘을 구매합니다.
• 유저가 모든 이모티콘을 구매한 뒤, 유저가 정해놓은 상한선 금액 이상이라면 이모티콘 플러스를 가입합니다.
  넘지 않는다면 금액을 더해줍니다.
• 우리가 원하는 것은 최대의 이모티콘 플러스 가입자 수, 가입자수가 같다면 가장 많은 금액을 창출하는 것이므로
  항상 이모티콘 가입자수와 금액비용을 비교해 주고 업데이트해줍니다.

📜전체 코드

#include <string>
#include <vector>

using namespace std;
int maxPlus=0;
int maxCost=0;

void funct(vector<int>sale,vector<vector<int>> users, vector<int> emoticons);
void sales(vector<int>sale,vector<vector<int>>users,vector<int>emoticons);
vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    vector<int>sale;
    sales(sale,users,emoticons);
    
    vector<int> answer;
    answer.push_back(maxPlus);
    answer.push_back(maxCost);
    return answer;
}
void sales(vector<int>sale,vector<vector<int>>users,vector<int>emoticons){

    if(sale.size()==emoticons.size()){
        funct(sale,users,emoticons);
        
        return;
    }
    for(int i=10; i<=40; i+=10){ //비율은 10%씩 증가함.
        sale.push_back(i);
        sales(sale,users,emoticons); //10, 20 , 30 , 40으로 돌리낟.
        sale.pop_back();
    }
}
void funct(vector<int>sale,vector<vector<int>> users, vector<int> emoticons){
    
    int emotPlus= 0;
    int total =0;
    for(int i=0; i<users.size();i++){
        int s=0;    
        for(int j=0; j<sale.size(); j++){

            if(users[i][0]>sale[j]){ //유저 할인률보다 낮으면 사질 못함
                continue;
            }
            s+= (emoticons[j]/100) *( 100-sale[j]);  //이모티콘 가격의 할인비율을 적용해서 더해줌.        
        }
        if(s>=users[i][1]){ //상한 금액을 넘는다면
            emotPlus++;
        }
        else{ //상한 금액을 안넘는다면
            total+=s; //금액을 더해줌.
        }
    }
    if(maxPlus>emotPlus){ //만약 가입자수가 적다면 되돌아감
        return ;
    }
    else if(maxPlus ==emotPlus && maxCost > total){ //이모티콘 플러스 가입자수가 같은데 코스트가 더 낮다면 되돌아감.
        return;
    }
    //위 조건에 해당하지 않는다면 값을 최신화해줌.
    maxCost=total;
    maxPlus = emotPlus;        
}

 

✔느낀 점

• 효율적으로 짜려고 하다가, 그냥 모든 경우의 수를 비교해도 된다고 생각했다.
  • 왜냐하면 이모티콘의 수가 최대 7개 이기에, 할인율의 종류도 4개 이므로, 시간 복잡도가 그렇게 크지 않다고 판단했다.