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

이모티콘 할인행사

 

• 내 풀이
  • 조합을 이용해서 각 상품에 대한 할인율 조합을 구함
  • 할인율 조합을 적용하여 전체 인원을 다 계산해보고
  • 최대의 이모티콘 플러스 가입자를 가지도록, 같다면 최대의 비용이 되도록 업데이트
• 에러사항
  • queue.append(tmp)로 넣었더니 0,0 이 들어감
  • tmp[:] 해서 복사해서 넣어야했음 왜지?

#n명에게 m개 할인 판매
#할인율 따라 이모티콘 사거나/ 플러스 가입
#할인율은 10%, 20%, 30%, 40% 
from collections import deque
#기준 할인율 이상의 이모티콘 모두 구매 -> 그 가격이 일정 가격 이상이면 플러스 가입
#플러스 가입자가 최대가 되도록
def solution(users, emoticons):
    answer = [0,0]
    discount=[10,20,30,40]
    n=len(emoticons)
    
    queue=deque()
    
    #모든 경우의 할인율 조합
    def dfs(tmp, cnt):
        if cnt==n:
            queue.append(tmp[:])
            return
        
        for d in discount:
            tmp[cnt]=d
            dfs(tmp, cnt+1)
            tmp[cnt]=0
    
    dfs([0 for _ in range(n)], 0)
    
    while queue:
        q=queue.popleft()
        plus=0
        total=0
        
        for user in users:
            cost=0
            for i in range(n):
                if user[0]<=q[i]:
                    cost+= emoticons[i]*(100-q[i])*0.01
                if cost>=user[1]:
                    plus+=1
                    break
            else:
                 total+=cost   
        
        if plus==answer[0]:
            answer[1]=max(total, answer[1])
        elif plus >answer[0]:
            answer[0]=plus
            answer[1]=total
        
    return answer