[Programmers] P150368 이모티콘 할인행사

[Programmers] P150368 이모티콘 할인행사

Question

Language: Python

이모티콘 할인 행사율에 따라 자신이 설정한 최소 할인율에 부합하면 이모티콘을 구입하고, 총 구입 금액이 예산을 넘어서면 이모티콘 플러스 서비스에 가입하게 된다. 이모티콘에 적용되는 할인율에 따라 서비스에 가입하는 가입자수가 달라지게 되는데, 이때 가입자수, 판매량이 최대가 되도록 만드는 것이 해당 문제의 과제이다.

이모티콘의 할인율에 따라 달라지게 되므로 모든 할인율의 조합을 적용해서 문제를 풀이하면 간단하게 해결 가능하다. 이모티콘의 갯수가 최대 7개 이므로 최대 4⁷의 조합에 대해 최대 100명의 유저를 조사하면 되므로 총 1,638,400개의 경우의 수를 조사하면 되므로 충분히 시간 내에 해결하는 것이 가능하다.

모든 이모티콘의 조합

all_discount_probabilities=[]
def find_all_situtations(max_depth,depth,discount_probabilities):
    global all_discount_probabilities
    if depth==max_depth:
        all_discount_probabilities.append(discount_probabilities)
        return
    
    for discount in [10,20,30,40]:
        find_all_situtations(max_depth,depth+1,discount_probabilities+[discount])

위와 같이 재귀문을 활용해도 되지만, python의 product+ repeat을 통해 중복순열을 쉽게 구할 수 있다.

product([10,20,30,40],repeat=length_of_emoticons)

Solution

from itertools import product

def solution(users, emoticons):
    answer = [0,0]
    length_of_emoticons=len(emoticons)
    discount_combinations=product([10,20,30,40],repeat=length_of_emoticons)
    
    for discount_combination in discount_combinations:
        registerd_users=0
        total_cost=0
        for discount_required,budget in users:
            cost=0
            for price, discount in zip(emoticons, discount_combination):
                if discount >= discount_required:
                    cost+=(price* (100-discount)//100)
                    
            if cost >= budget:
                registerd_users+=1
            else:
                total_cost+=cost
                
        answer=max(answer,[registerd_users,total_cost])
    
    
    return answer