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

난이도 : LV 2

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/150368

문제해결 아이디어

• 문제의 핵심

  • user는 각각의 기준이 되는 할인율이 있고, 그 기준을 넘는 할인율이면 이모티콘을 구매한다.
  • 구매한 이모티콘들의 가격의 합이 user의 기준 금액보다 크다면 이모티콘 플러스를 가입한다.
  • 이모티콘 플러스 가입자수가 최대가 되게하는게 먼저, 이모티콘 판매금액은 그 이후의 우선순위를 가진다.

• 이모티콘 할인율은 [40,30,20,10] 중 하나이고 이모티콘의 종류는 7이하이다.

• 모든 경우의 수를 다 확인해서 문제조건을 만족하는 최댓값을 찾는다.

• 백트래킹을 활용해서 풀수도있다. 하지만 필자는 product(중복순열)을 통해 이모티콘별 할인율을 가지는 모든 경우의 수를 for문 돌리는 식으로 했다.

소스코드

from itertools import product

def solution(users, emoticons):
    n = len(users)
    m = len(emoticons)
    sales = [40,30,20,10]
    ans = [0,0]
    for k in product(sales, repeat=m):
        plus = price = 0
        for s,p in users: #유저의 기준할인율, 기준 금액
            cnt = 0
            for i in range(len(emoticons)):
                if s <= k[i]: #기준할인율보다  높으면
                    cnt += emoticons[i] * (100 - k[i]) // 100 #구매
				
                if cnt >= p: #만약 기준 금액보다 구매액이 높다면 플러스 가입
                    plus += 1
                    break
            else: #플러스를 가입하지 않았다면 그냥 이모티콘 구매액을 추가해줌
                price += cnt
        
        if plus > ans[0] or (plus == ans[0] and price > ans[1]):  #최댓값 비교
            ans = [plus, price]
    return ans