PGS 이모티콘 할인행사

URL

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

태그

구현

브루트포스 알고리즘

문제 설명

•

이모티콘 할인율을 조정하여 이모티콘 플러스 서비스 가입자를 최대화하고, 그 다음으로 이모티콘 매출액을 최대화하는 최적의 할인율 조합을 찾아 가입자 수와 매출액을 반환하는 문제

예제 입력/출력

users	emoticons	result
[[40, 10000], [25, 10000]]	[7000, 9000]	[1, 5400]
[[40, 2900], [23, 10000], [11, 5200], [5, 5900], [40, 3100], [27, 9200], [32, 6900]]	[1300, 1500, 1600, 4900]	[4, 13860]

제약 조건

•

1≤n≤1001 ≤ n ≤ 1001≤n≤100

•

1≤m≤71 ≤ m ≤ 71≤m≤7

•

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

문제 풀이

•

접근1 모든 할인율의 조합을 완전 탐색하는 방법 - O(4m⋅n⋅m)O(4^m \cdot n \cdot m)O(4m⋅n⋅m)

◦

할인율 조합 탐색 (DFS) - O(4m)O(4^m)O(4m)

▪

각 이모티콘에 대해 선택할 수 있는 할인율은 4가지 (10%, 20%, 30%, 40%)

▪

이모티콘의 개수를 mmm이라고 할 때, 할인율의 조합 수는 4m4^m4m

◦

각 조합에 대해 결과를 계산 - O(n⋅m)O(n \cdot m)O(n⋅m)

◦

즉, 최악의 경우 11,468,800 회 연산이 필요

풀이 코드

def calculate_result(discounts):
    global users, emoticons
    """ 조합된 할인율로 결과를 시뮬레이션 하는 함수 """
    result = [0, 0]  # (가입자 수, 매출액)
    
    for user_discount, user_limit in users:
        money = 0
        for emoticon_price, discount in zip(emoticons, discounts):
            if discount >= user_discount:
                money += emoticon_price * (100 - discount) // 100
        if money >= user_limit:
            result[0] += 1
        else:
            result[1] += money
    return result

def dfs(discounts, depth):
    """ 모든 경우의 할인율 조합을 구하는 함수 """
    global answer
    
    # Base Case
    if depth == len(discounts):
        answer = max(answer, calculate_result(discounts))
        return
    
    # Recursive Case
    for p in [10, 20, 30, 40]:
        discounts[depth] += p
        dfs(discounts, depth + 1)
        discounts[depth] -= p

def solution(_users, _emoticons):
    global users, emoticons, answer
    users = _users
    emoticons = _emoticons
    
    discounts = [0] * len(emoticons) # 상품 별 할인율
    answer = [0, 0] # (가입자 수, 매출액)
    dfs(discounts, 0)
    return answer
Python
복사