from itertools import product
def solution(users, emoticons):
answer = []
m = len(emoticons)
discount = [10, 20, 30, 40]
cases = list(product(discount, repeat=m))
for case in cases:
sub = 0
amount = 0
prices = []
for i in range(m):
prices.append((emoticons[i] // 100) * (100 - case[i]))
for target, threshold in users:
money = 0
for i in range(m):
if case[i] >= target:
money += prices[i]
if money >= threshold:
sub += 1
else:
amount += money
answer.append((sub, amount))
answer.sort(key=lambda x: (-x[0], -x[1]))
return answer[0]
문제 정의
이모티콘의 할인율을 탐색했을 때
서비스 가입자, 매출액의 최댓값을 찾는 문제이다.
(서비스 가입자가 같으면 매출액이 최대가 되도록)
시간 복잡도 계산
완전 탐색이 먼저 가능한지 계산해 봤다.
먼저 가능한 이모티콘의 가격들은 중복조합으로 구할 수 있고
4^7이기 때문에 약 16,000이다.
또한 user의 수가 최대 100이기 때문에 총 탐색 범위는 약 1,600,000이다.
따라서 충분히 완전 탐색이 가능하다고 판단했다.
문제 풀이
itertools.product 라이브러리로 중복조합을 생성해 주었으며
문제에 조건에 따라 계산해 주고 마지막엔 (가입자 수, 매출액) 기준으로 정렬해 주었다.
예외 사항
기타 특이사항 없음.