이모티콘 할인행사 (완전 탐색, 조합)

def solution(users, emoticons):

    from itertools import product
    answer = [0, 0]

    # 모든 할인율 중복 조합
    combi = product((40, 30, 20, 10), repeat=len(emoticons))
    for discounts in combi:

        sold = [0, 0]  # 이모티콘, 판매액

        # 각 유저
        for user_discount, user_money in users:

            sold_emoticons = 0

            # 각 이모티콘과 할인율
            for emoticon, discount in zip(emoticons, discounts):

                # 사용자 할인율 기준보다 많이 할인하면 구매
                if discount >= user_discount:
                    sold_emoticons += emoticon * (1 - discount / 100)
                    # print("sold_emoticons", int(sold_emoticons))


            # 구매비용이 임티플러스 기준금액보다 크면 임티플러스 가입
            if sold_emoticons >= user_money:
                sold[0] += 1
            else: # 아니면 그냥 구매
                sold[1] += sold_emoticons

        # print(answer)
        answer = max(answer, sold)
    return answer

print(solution([[40, 10000], [25, 10000]], [7000, 9000] ))

 

 

zip() 기본 문법

zip() 함수는 여러 개의 순회 가능한(iterable) 객체를 인자로 받고

각 객체가 담고 있는 원소를 튜플의 형태로 차례로 접근할 수 있는 반복자(iterator)를 반환

numbers = [1, 2, 3]
letters = ["A", "B", "C"]
for pair in zip(numbers, letters):
	print(pair)
    
(1, 'A')
(2, 'B')
(3, 'C')

 

이 문제는 가능한 모든 경우의 수를 탐색하면 해결할 수 있는 문제입니다. 

 

각 이모티콘은 10%, 20%, 30%, 40%의 4가지 할인율을 가질 수 있습니다.

만약 이모티콘이 m개가 있다면, 각 이모티콘에 4가지 중 하나의 할인율을 적용할 수 있으므로 이모티콘을 할인하는 모든 경우의 수는 4^m 가지가 될 것입니다. 

 

그런데 이모티콘의 최대 개수는 7개로 매우 적으며, 경우의 수는 최대 4^7인 16,384가지밖에 되지 않기 때문에 제한 시간 안에 모든 경우의 수를 탐색할 수 있습니다.

 

각 이모티콘에 할인율을 적용한 다음에는 각 사용자들이 이모티콘 구매에 돈을 얼마를 쓰게 되는지를 구합니다.

이것은 사용자 수를 n, 이모티콘 수를 m이라 했을 때, 간단한 반복문과 조건문을 통해서 O(n × m)에 구할 수 있습니다.

 

각 사용자가 이모티콘 구매에 돈을 얼마를 쓰는지 구합니다. 이모티콘 구매 비용이 기준 비용보다 더 든다면, 구매 비용을 0으로 만들고 이모티콘 플러스 가입자 수에 1을 더해줍니다. 그렇지 않다면 이모티콘 판매액에 비용을 더해줍니다.

 

이모티콘에 할인율을 적용하는 모든 경우의 수에 대해서 이 과정을 반복한다면 시간복잡도 O(4^n × n × m)의 문제를 해결할 수 있습니다.