문제
Programmers: 이모티콘 할인행사
- 설명: 사용자가 이모티콘의 구매 기준과 이모티콘의 가격이 주어질 때 아래 조건을 만족하도록 이모티콘의 할인율을 결정하라.
- 이모티콘 플러스 서비스 가입자를 최대로
- 이모티콘 판매액을 최대로
풀이
- 모든 이모티콘의 할인율을 결정하는데 $4^7$
- 왜? 이모티콘의 할인율은 $4$개로 고정되어있다. $(10\%, 20\%, 30\%, 40\%)$
- 할인율이 결정된 후 이모티콘 플러스 서비스 가입자와 이모티콘 판매액 구하는데 $nm = 100 \times 7$
- 따라서
Backtracking
$+$ Bruteforcing
을 통해 구하면 된다.
오늘의 회고
Backtracking
의 경계조건을 $n$으로 두어서 시간초과가 무한히 발생했다.
- 위의 오류를 해결하려고 미리 이모티콘의 할인율에 따라 테이블을 정해두려 했지만, 문제 특성상 그럴 수가 없었다.
- 경계조건을 $m$으로 두니 $3$개를 제외하고 틀렸다.
- 할인 받은 이모티콘을 구하는데 소수 계산을 통해서 했기 때문에 오차가 발생한 것이라고 예상하였고,
- 이모티콘의 가격이 $100$의 배수라는 점을 확인한 후 정수 연산으로 변경해주었다.
Code
# Programmers150368.py
def solution(users, emoticons):
n = len(users)
m = len(emoticons)
ans = []
curr_discount = []
def solve(idx):
if idx == m:
result = [0, 0]
for want_discount, threshold in users:
sum_of_buy = 0
for price, discount in zip(emoticons, curr_discount):
if want_discount <= discount:
discount_price = price // 100 * discount
sum_of_buy += int(price - discount_price)
if sum_of_buy >= threshold:
result[0] += 1
else:
result[1] += sum_of_buy
ans.append(result)
else:
for discount in [10, 20, 30, 40]:
curr_discount.append(discount)
solve(idx + 1)
curr_discount.pop()
solve(0)
return sorted(ans, reverse=True)[0]