선밥의 공부하는 블로그

이모티콘 할인행사

문제 링크

이모티콘 할인행사

분석

이모티콘마다 할인율을 결정해야 합니다.
할인율은 10%, 20%, 30%, 40%가 있습니다.

사용자는 각각 이모티콘 구매 기준 할인율과 이모티콘 플러스 서비스 구매 기준 가격을 가지고 있습니다.
사용자는 기준 할인율 이상인 이모티콘만 구매합니다.
구매한 이모티콘 금액 합이 이모티콘 플러스 서비스 구매 기준 가격 이상이면 이모티콘을 구매하지 않고, 이모티콘 플러스를 가입합니다.

이모티콘 플러스 가입자 수를 최대화하고, 가입자 수가 같다면 이모티콘 판매액을 최대화합니다.

DFS를 사용하여 모든 경우의 수를 완전탐색하여 풀어낼 수 있습니다.

풀이

#include <vector>
#include <algorithm>

using namespace std;

// 가입자 수와 총 판매액을 저장
vector<int> answer = {0, 0};
// 사용할 수 있는 할인율 종류
vector<int> discountRates = {10, 20, 30, 40};

// 모든 이모티콘 할인 조합을 탐색한다.
void dfs(const vector<vector<int>>& users, const vector<int>emoticons, int index, vector<int>& discounts)
{
    // 이모티콘의 총 개수
    int n = emoticons.size();
    
    // 모든 이모티콘에 대해 할인율을 다 정했을 경우
    if (index == n)
    {
        // 현재 할인 조합에서의 총 가입자수 및 총 판매 금액
        int totalSubscriber = 0;
        int totalSale = 0;
        
        // 모든 사용자에 대해 반복
        for (auto & user : users)
        {
            // 현재 사용자가 구매하게되는 총 금액
            int purchaseAmount = 0;
            
            // 각 이모티콘에 대해 반복
            for(int i = 0; i < n; ++i)
            {
                // 이모티콘의 할인율이 사용자의 기준에 적합한 경우
                if (discounts[i] >= user[0])
                {
                    // 할인 적용된 이모티콘 가격 계산 및 구매 금액 누적
                    int price = emoticons[i] * (100 - discounts[i]) / 100;
                    purchaseAmount += price;
                }
            }
            
            // 사용자의 구매 금액이 플러스 가입 기준 이상이라면 가입
            if (purchaseAmount >= user[1])
            {
                ++totalSubscriber;
            }
            // 기준에 미치지 못한다면 구매한 금액만 누적한다.
            else
            {
                totalSale += purchaseAmount;
            }
        }
        
        // 현재 할인 비율의 결과가 기존보다 구독자 수가 많거나 같아도 판매금액이 많다면 갱신한다.
        if (totalSubscriber > answer[0] || (totalSubscriber == answer[0] && totalSale > answer[1]))
        {
            answer[0] = totalSubscriber;
            answer[1] = totalSale;
        }
        
        return;
    }
    
    // 아직 모든 이모티콘에 대해 할인율을 정하지 않은 경우
    for (int rate : discountRates)
    {
        // 현재 이모티콘에 할인율 적용 및 다음 이모티콘으로 이동
        discounts[index] = rate;
        dfs(users, emoticons, index + 1, discounts);
    }
}

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    // 이모티콘마다 할인율을 저장할 배열
    vector<int> discounts(emoticons.size(), 0);
    
    // DFS를 사용한 모든 할인 조합 탐색
    dfs(users, emoticons, 0, discounts);
    
    return answer;
}

성능 요약

시간 복잡도는 $O(4^n \times m \times n)$입니다.

  • DFS의 재귀호출 횟수 $O(4^n)$
    • n은 이모티콘 수를 의미합니다.
  • 모든 사용자를 대상으로 이모티콘을 사는지 구독하는지 검사 $O(m \times n)$
    • m은 사용자 수를 의미합니다.
  • $O(4^n \times m \times n)$

공간 복잡도는 $O(n)$입니다.

  • 재귀 호출 스택 $O(n)$
  • 각 이모티콘마다 현재 적용 중인 할인율 저장하는 벡터 vector<int> discounts $O(n)$
  • $O(n) + O(n)$
테스트 성능

테스트 1 〉 통과 (0.01ms, 4.22MB)
테스트 2 〉 통과 (0.01ms, 4.21MB)
테스트 3 〉 통과 (0.02ms, 4.14MB)
테스트 4 〉 통과 (0.05ms, 4.17MB)
테스트 5 〉 통과 (0.08ms, 3.69MB)
테스트 6 〉 통과 (0.05ms, 4.14MB)
테스트 7 〉 통과 (0.31ms, 4.17MB)
테스트 8 〉 통과 (0.17ms, 4.23MB)
테스트 9 〉 통과 (1.24ms, 4.2MB)
테스트 10 〉 통과 (0.67ms, 4.24MB)
테스트 11 〉 통과 (5.42ms, 4.15MB)
테스트 12 〉 통과 (2.83ms, 4.2MB)
테스트 13 〉 통과 (21.57ms, 4.21MB)
테스트 14 〉 통과 (20.00ms, 4.23MB)
테스트 15 〉 통과 (1.22ms, 4.13MB)
테스트 16 〉 통과 (1.16ms, 4.21MB)
테스트 17 〉 통과 (0.02ms, 4.21MB)
테스트 18 〉 통과 (0.37ms, 3.64MB)
테스트 19 〉 통과 (0.01ms, 4.02MB)
테스트 20 〉 통과 (0.01ms, 4.14MB)

Programmers 카테고리 내 다른 글 보러가기

댓글남기기

최근 글