728x90
def solution(users, emoticons):
from itertools import product
answer = [0, 0]
# 모든 할인율 중복 조합
combi = product((40, 30, 20, 10), repeat=len(emoticons))
for discounts in combi:
sold = [0, 0] # 이모티콘, 판매액
# 각 유저
for user_discount, user_money in users:
sold_emoticons = 0
# 각 이모티콘과 할인율
for emoticon, discount in zip(emoticons, discounts):
# 사용자 할인율 기준보다 많이 할인하면 구매
if discount >= user_discount:
sold_emoticons += emoticon * (1 - discount / 100)
# print("sold_emoticons", int(sold_emoticons))
# 구매비용이 임티플러스 기준금액보다 크면 임티플러스 가입
if sold_emoticons >= user_money:
sold[0] += 1
else: # 아니면 그냥 구매
sold[1] += sold_emoticons
# print(answer)
answer = max(answer, sold)
return answer
print(solution([[40, 10000], [25, 10000]], [7000, 9000] ))
zip() 기본 문법
zip() 함수는 여러 개의 순회 가능한(iterable) 객체를 인자로 받고
각 객체가 담고 있는 원소를 튜플의 형태로 차례로 접근할 수 있는 반복자(iterator)를 반환
numbers = [1, 2, 3]
letters = ["A", "B", "C"]
for pair in zip(numbers, letters):
print(pair)
(1, 'A')
(2, 'B')
(3, 'C')
더보기
이 문제는 가능한 모든 경우의 수를 탐색하면 해결할 수 있는 문제입니다.
각 이모티콘은 10%, 20%, 30%, 40%의 4가지 할인율을 가질 수 있습니다.
만약 이모티콘이 m개가 있다면, 각 이모티콘에 4가지 중 하나의 할인율을 적용할 수 있으므로 이모티콘을 할인하는 모든 경우의 수는 4^m 가지가 될 것입니다.
그런데 이모티콘의 최대 개수는 7개로 매우 적으며, 경우의 수는 최대 4^7인 16,384가지밖에 되지 않기 때문에 제한 시간 안에 모든 경우의 수를 탐색할 수 있습니다.
각 이모티콘에 할인율을 적용한 다음에는 각 사용자들이 이모티콘 구매에 돈을 얼마를 쓰게 되는지를 구합니다.
이것은 사용자 수를 n, 이모티콘 수를 m이라 했을 때, 간단한 반복문과 조건문을 통해서 O(n × m)에 구할 수 있습니다.
각 사용자가 이모티콘 구매에 돈을 얼마를 쓰는지 구합니다. 이모티콘 구매 비용이 기준 비용보다 더 든다면, 구매 비용을 0으로 만들고 이모티콘 플러스 가입자 수에 1을 더해줍니다. 그렇지 않다면 이모티콘 판매액에 비용을 더해줍니다.
이모티콘에 할인율을 적용하는 모든 경우의 수에 대해서 이 과정을 반복한다면 시간복잡도 O(4^n × n × m)의 문제를 해결할 수 있습니다.
728x90