2-10. 코딩 테스트 기출 문제 [프로그래머스 이모티콘 할인 행사]

다나·2023년 2월 21일

코딩테스트 스터디

목록 보기

24/32

1. 관련 문제 🎯

문제 : 프로그래머스 이모티콘 할인 행사 😃
난이도 : LEVEL 2

2. 문제 소개 🧩

2-1. 문제(이모티콘 할인 행사) 목표

카카오톡에서는 이모티콘 할인 행사를 하는데, 목표는 다음과 같다.
이때, 1번 목표가 우선이며, 2번 목표가 그 다음입니다.
1️⃣ 이모티콘 플러스 서비스 가입자를 최대한 늘리는 것.
2️⃣ 이모티콘 판매액을 최대한 늘리는 것.

2-2. 문제(이모티콘 할인 행사)의 진행 방식

n명의 카카오톡 사용자들에게 이모티콘 m개를 할인하여 판매한다.

이모티콘마다 할인율은 다를 수 있으며, 할인율은 10%, 20%, 30%, 40% 중 하나로 설정된다.

카카오톡 사용자들은 2개의 기준을 따라 이모티콘을 사거나, 이모티콘 플러스 서비스에 가입한다.
1️⃣ 각 사용자들은 자신의 기준에 따라 일정 비율 이상 할인하는 이모티콘을 모두 구매한다.
2️⃣ 각 사용자들은 자신의 기준에 따라 이모티콘 구매 비용의 합이 일정 가격 이상이 된다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입한다.

3. 문제 풀이 🖌️

☝️ 위의 예시를 아래와 같이 나타낼 수 있다!

✌️ 이때, 이모티콘 1과 이모티콘 2의 가격을 10%, 20%, 30%, 40%를 적용한 경우를 모두 나타낸다.

이모티콘 1과 이모티콘 2 가격표를 한 개씩 적용해보면서 사용자 1과 사용자 2가 해당 이모티콘을 구매할 지와 이모티콘 플러스 서비스를 가입할 지를 구한다.

위처럼 가격표의 끝까지 구해보면 아래와 같이 각각의 할인 가격에 따른 이모티콘 플러스 서비스 가입자수와 이모티콘 총 판매액을 구할 수 있다.

이때, 문제의 목표를 유의해서 정답을 구해보자!
1️⃣ 최대 이모티콘 플러스 서비스 가입자
2️⃣ 최대 이모티콘 판매액
➡️ 따라서 이모티콘 플러스 서비스 가입자수가 최대인 경우, 이모티콘 총 판매액이 최대를 고르면 된다.

위 표의 경우, 이모티콘 플러스 서비스 가입자수가 1명이 최대이고 1명일 때 이모티콘 총 판매액은 4200원, 5400원, 0원으로 최대 금액은 5400원이다!

🔥 답은 이모티콘 플러스 서비스 가입자수는 1명, 이모티콘 총 판매액은 5400원이다.

이때, 우선순위 큐를 사용하면 priority_queue<pair<int,int>> pq pair에서 첫번째 값을 우선적으로 정렬되고 첫번째 값이 같다면 두번째 값으로 정렬된다.
따라서, 우선순위 큐에 {이모티콘 플러스 서비스 가입자수, 이모티콘 총 판매액} 순서대로 넣어주면 문제의 목표 순서대로 정렬된다.

이때, 가장 중요한 것은 중복 순열을 구하는 것이다!!
이모티콘별로 가격표를 구하기 위해서는 10%, 20%, 30%, 40% 중에서 할인율을 적용한다.
여기에서 중복 순열을 사용하여 이모티콘에 적용되는 할인율을 구해야 한다.
ex) 이모티콘이 2개인 경우 : (40%, 40%), (40%,30%) ...
🔥 중복 순열은 다음 페이지에서 다루어보자~!
https://velog.io/@da_na/순열-조합-알고리즘

4. 전체 코드 🔑

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

int sales[4] = {10, 20, 30, 40};
vector<double> sale;
priority_queue<pair<int,int>> pq;

void permutation_r(vector<vector<int>> users, vector<int> emotis){
    if(sale.size() == emotis.size()){
        int emoticons_plus = 0; //이모티콘 플러스 서비스 가입자수
        int prices_sum = 0;  //총 판매액
        
        for(int i=0; i<users.size(); i++){
            int price = 0;
            for(int j=0; j<emotis.size(); j++){
                if( sale[j] >= users[i][0]){
                    price += (emotis[j] * (100-sale[j])/100);
                }
            }
            if(price >= users[i][1]){
                emoticons_plus++;
            }
            else{
                prices_sum+=price;
            }
        }
        pq.push({emoticons_plus, prices_sum});
        return;
    }
    
    for(int i=0; i<4; i++){
        sale.push_back(sales[i]);
        permutation_r(users, emotis);
        sale.pop_back();
    }
}

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {    
    permutation_r(users, emoticons);
    return {pq.top().first, pq.top().second};
}