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

이얀조·2023년 1월 13일
0

🎀프로그래머스

목록 보기
5/21
post-thumbnail

📢 문제 설명


카카오톡에서는 이모티콘을 무제한으로 사용할 수 있는 이모티콘 플러스 서비스 가입자 수를 늘리려고 합니다.
이를 위해 카카오톡에서는 이모티콘 할인 행사를 하는데, 목표는 다음과 같습니다.
1. 이모티콘 플러스 서비스 가입자를 최대한 늘리는 것.
2. 이모티콘 판매액을 최대한 늘리는 것.
1번 목표가 우선이며, 2번 목표가 그 다음입니다.
이모티콘 할인 행사는 다음과 같은 방식으로 진행됩니다.
n명의 카카오톡 사용자들에게 이모티콘 m개를 할인하여 판매합니다.
이모티콘마다 할인율은 다를 수 있으며, 할인율은 10%, 20%, 30%, 40% 중 하나로 설정됩니다.
카카오톡 사용자들은 다음과 같은 기준을 따라 이모티콘을 사거나, 이모티콘 플러스 서비스에 가입합니다.
각 사용자들은 자신의 기준에 따라 일정 비율 이상 할인하는 이모티콘을 모두 구매합니다.
각 사용자들은 자신의 기준에 따라 이모티콘 구매 비용의 합이 일정 가격 이상이 된다면, 
이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입합니다.
카카오톡 사용자 n명의 구매 기준을 담은 2차원 정수 배열 users, 
이모티콘 m개의 정가를 담은 1차원 정수 배열 emoticons가 주어집니다. 
이때, 행사 목적을 최대한으로 달성했을 때의 이모티콘 플러스 서비스 가입 수와 
이모티콘 매출액을 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요.

🏕 제한사항

  • 1 ≤ users의 길이 = n ≤ 100
    • users의 원소는 [비율, 가격]의 형태입니다.
    • users[i]i+1번 고객의 구매 기준을 의미합니다.
    • 비율% 이상의 할인이 있는 이모티콘을 모두 구매한다는 의미입니다.
      • 1 ≤ 비율 ≤ 40
    • 가격이상의 돈을 이모티콘 구매에 사용한다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입한다는 의미입니다.
      • 100 ≤ 가격 ≤ 1,000,000
      • 가격은 100의 배수입니다.
  • 1 ≤ emoticons의 길이 = m ≤ 7
    • emoticons[i]i+1번 이모티콘의 정가를 의미합니다.
    • 100 ≤ emoticons의 원소 ≤ 1,000,000
    • emoticons의 원소는 100의 배수입니다.

🥝 풀이

이 문제의 포인트는 백트래킹 이였다.
특히 조건에서 emoticons 의 길이는 최대 7, 그리고 할인율은 10%, 20%, 30%, 40% 라고 하였기 때문에 이모티콘의 최대 경우의 수는 4 ^ 7 = 2 ^ 14 정도 이다.

그 다음으로는 문제에서 제시한 조건인
1. 이모티콘 플러스 서비스 가입자를 최대한 늘리는 것.
2. 이모티콘 판매액을 최대한 늘리는 것.
(1번 목표가 우선이며, 2번 목표가 그 다음입니다.)

부분이라고 생각한다.

백트래킹에 앞서 어떻게 재귀적으로 가면 좋을지를 고민해 보았다.

위와 같이 이모티콘의 종류 각각의 할인율을 이용하여 금액을 추적해 나가는 방식으로 진행하였다.

문제의 첫번째 테스트 케이스를 이용하여 예시를 들어 보면 E1의 가격은 7000원, E2 의 가격은 9000원이며 두명의 user가 각각 40%, 25% 할인율일 경우 구매한다고 명시되어있다.

그 중 이모티콘1(E1) 의 할인율을 40%, 이모티콘2(E2)의 할인율을 30% 라고 하였을 때의 경우를 보면 다음과 같이 계산할 수 있다.

먼저 E1에 해당하는 재귀에서 40%의 할인율을 가지고 계산을 진행한다.
두 user 모두 원하는 할인율 보다 높거나 같기 때문에 E1을 구매할 것이다.
이후 E2 분기로 넘어갈 경우 30%의 할인율을 가지고 계산을 진행한다.

user1의 경우 40%이상의 경우에만 구매하기 때문에 구매하지 않게 된다.
그렇게 되면 user1은 총 4200 원, user2는 10500 원으로 이모티콘 플러스를 구매하게 되며 answer = [1, 4200] 이라는 결과를 얻게 된다.

하지만 E1 -> 30%, E2 -> 40% 인 경우라면 다음과 같다.
와 같은 분기로 진행한다.

user1은 E1을 구매하지 못하며, user2는 E1를 구매하여 4900 원의 cost가 쌓이게 된다.

이후 E2는 다음과 같다.

두 user가 모두 구매하여, user1은 5400원, user2는 총 10300 원을 사용하여 이모티콘 플러스를 구매한다.
위의 경우는 answer = [1, 5400] 으로 이모티콘 플러스의 수는 동일하나 더 높은 값을 얻을 수 있다.

따라서 각 이모티콘의 할인율에 따른 분기를 이용하여 user가 사용하는 총 금액을 구하고 이후 이모티콘 플러스 구매 한도 금액을 넘은 경우 이모티콘 플러스 구매 수를 체킹하는 방식으로 진행한다면 충분히 해결할 수 있는 문제였다.

🐷 코드

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

vector<int> discounts = {40, 30, 20, 10};
void getResult(int idx, vector<vector<int>> users, vector<int> emoticons, vector<int>* userCost, int* Plus, int* Cost);
vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    vector<int> answer, userCost(users.size(), 0);
    int maxPlus = -1, maxCost = -1;
    
    // start back tracking
    getResult(0, users, emoticons, &userCost, &maxPlus, &maxCost);
    answer.push_back(maxPlus);
    answer.push_back(maxCost);
    
    return answer;
}

void getResult(int idx, vector<vector<int>> users, vector<int> emoticons, vector<int>* UserCost, int* Plus, int* Cost) {
    vector<int> userCost = *UserCost;
    
    if (idx >= emoticons.size()) {
        int maxPlus = 0, maxCost = 0;
        
        // calc Answer
        for (int i = 0; i < userCost.size(); i++) {
            if (userCost[i] >= users[i][1]) maxPlus += 1;
            else maxCost += userCost[i];
        }
        
        if (maxPlus >= Plus[0]) {
            if ((maxPlus > Plus[0]) || (maxPlus == Plus[0] && maxCost >= Cost[0])) {
                Plus[0] = maxPlus;
                Cost[0] = maxCost;
            }
        }
        
        return;   
    }
    
    for (int i = 0; i < discounts.size(); i++) {
        int discount = discounts[i];
        
        // able Emoticon get
        for (int j = 0; j < users.size(); j++) {
            if (users[j][0] <= discount) userCost[j] += emoticons[idx] * (100 - discount) / 100;
        }
        
        // get Next Emoticons
        getResult(idx + 1, users, emoticons, &userCost, Plus, Cost);
        
        // return Cost
        for (int k = 0; k < users.size(); k++) {
            if (users[k][0] <= discount) userCost[k] -= emoticons[idx] * (100 - discount) / 100;
        }
    }
}

🥉 어려웠던 점

1. 레퍼런스를 이용하여 함수 인자로 전달하는 것
→ 기존에 answer 벡터를 레퍼런스로 하여 함수인자로 전달하였는데, 제대로 값이 변하지 않았다. 따라서 따로 int 변수를 만들어 레퍼런스로 전달하니 제대로 값이 변한 부분에 대해 조금 더 공부할 필요가 있어보인다.
2. 백트래킹 과정
→ 전체 user에게 할인된 이모티콘 가격을 할당한 후 다음 이모티콘 분기로 넘어갔어야 했는데 잘못된 백트래킹 과정을 수행하여 잘못된 결과를 얻게 되었다. 조금 더 익숙해져야 할 것 같다.

profile
이얀조다!

0개의 댓글