[프로그래머스] 이모티콘 할인행사

프로그래머스

<조건>

1. 이모티콘 플러스를 최대한 늘리는 것

2. 이모티콘 플러스 가입자가 같다면 이모티콘 구매 비용이 높을 수록 좋다

<풀이>

1. 탐색문제

2. 탐색 시간 -> 어떻게 줄일 수 있을까?

• 이분 탐색, dp, greedy 같은 알고리즘을 적용해서 시간을 줄이는 문제
• 완전 탐색 -> 탐색시간을 어떻게 해도 줄알 수 없는 경우 / 혹은 완전 탐색을 써도 될때

3. 탐색 시간 계산

• 완전탐색을 한다면 시간은 얼마나 걸리지? -> 대략 1억 미만이면 가능이라고 판단

from itertools import product

def solution(users, emoticons):
    answer = [0,0]
    cases = [10,20,30,40]
    for case in product(cases, repeat=len(emoticons)): # 완전탐색
        total_pay , plus_num = 0, 0
        for rate, price in users:
            pay = 0
            for i, emoticon in enumerate(emoticons):
                if case[i] >= rate: #구매함
                    pay += emoticon * (100 - case[i]) //100
            if pay >= price: # 가입함
                plus_num += 1
            else: #가입안하고 구매만
                total_pay += pay
        
        if plus_num > answer[0]: #이모티콘 가입자 수 증가
            answer[0] , answer[1] = plus_num, total_pay
        elif plus_num == answer[0] and total_pay >  answer[1]: #매출액만 증가 
            answer[1] = total_pay
    
    return answer