[kakako 2023] 이모티콘 할인행사 풀이

아이디어 도출 방법

아래의 목표를 달성하기 위해서는 각 이모티콘에 적용할 할인률에 대한 모든 경우의 수를 계산해야 한다.

왜냐하면 어떤 이모티콘에 무슨 할인률을 적용하는지에 따라서 1번과 2번 목표의 값이 달라지기 때문이다.

1. 이모티콘 플러스 서비스 가입자를 최대한 늘리는 것.
2. 이모티콘 판매액을 최대한 늘리는 것.

각 이모티콘에 대해서 각각의 할인률을 조합하기 위해서 카타시안 곱을 사용한다.

카타시안 곱이란 간단히 말하면 모든 조합을 구하는 것이다.

A ={1, 2, 3}, B = {5, 6, 7}

A X B의 결과는 {1, 5}, {1, 6}, {1, 7},  {2, 5}, {2, 6}, {2, 7}, {3, 5}, {3, 6}, {3, 7}이 된다. 

우리의 경우 각 이모티콘에 적용할 할인률만 구하면 되기 때문에 "discounts * discounts ----"이 된다. 코드 상에서는 'product(discount, repeat=len(emoticons)이다

 

시간복잡도는 O(4^7 * 100) = 이모티콘의 경우의 수(4^7) * 해당 경우의 최대 users 수(100) 

최종 결과

from itertools import product

def solution(users, emoticons):
    answer = [0, 0]
    discount = [0.1, 0.2, 0.3, 0.4]

    for pick in product(discount, repeat=len(emoticons)):

        can_get_moeny = 0
        join_emoji_club = 0

        for user in users:
            discount_need = user[0] / 100
            upper_limit = user[1]
            total_money = 0

            for sale, price in zip(pick, emoticons):
                if discount_need <= sale:
                    total_money += price *  (1 - sale)
            
            if upper_limit <= total_money:
                total_money = 0
                join_emoji_club += 1
            
            can_get_moeny += total_money
        
        answer = max(answer, [join_emoji_club, can_get_moeny])

    return answer



if __name__ == "__main__":
    users = [[40, 10000], [1, 10000]]
    emoticons = [7000, 9000]
    result = [1, 5400]

    print(solution(users, emoticons))

 

후기

카타시안 곱에 대해서 처음 접했다. 완전탐색을 굉장히 쉽게 만들 수 있었다.

또한 max에 배열을 넣으면 자동으로 처리하는 것도 처음 알았다.