이모티콘 할인행사

해결 방법

• 가입자를 최대한 늘리게 하기 위해서는 어떻게 해야할까?
• 내가 조절 할 수 있는건 각 이모티콘의 할인율이다.
• 할인율을 조절을 어떻게 잘 해야 가입자 수를 늘릴 수 있을까?
• 이모티콘의 길이는 7이고 할인율은 10,20,30,40 퍼중 하나로 설정된다.
• 나올 수 있는 할인율 가지수는 총 4^7승=16384이기 때문에 충분히 브루트 포스로 모든 걸 다 확인할 수 있다.
• backtracking을 사용하면 해결 할 수 있겠다고 생각

코드

answer = [-1,-1]

def solution(users, emoticons):
    n = len(users)
    m = len(emoticons)
    discount = [10, 20, 30, 40]
    discount_list = [0]*m
    
    
    def back_tracking(idx):
        global answer
        if(idx==m):
            total_cost = 0
            total_reg = 0
            for i in range(n):
                tmp_cost = 0
                for j in range(m):
                    if(users[i][0]<=discount_list[j]):
                        tmp_cost += emoticons[j] * (100-discount_list[j])/100
                if(tmp_cost >= users[i][1]):
                    tmp_cost = users[i][1]
                    total_reg+=1
                else:
                    total_cost+=tmp_cost
            if(answer[0] < total_reg):
                answer = [total_reg, total_cost]
            elif(answer[0] == total_reg and answer[1] < total_cost):
                answer[1] = total_cost
            return
        else:
            for i in range(4):
                discount_list[idx] = discount[i]
                back_tracking(idx+1)
    back_tracking(0)
    return answer