문제

Programmers: 이모티콘 할인행사

설명: 사용자가 이모티콘의 구매 기준과 이모티콘의 가격이 주어질 때 아래 조건을 만족하도록 이모티콘의 할인율을 결정하라.
1. 이모티콘 플러스 서비스 가입자를 최대로
2. 이모티콘 판매액을 최대로

풀이

모든 이모티콘의 할인율을 결정하는데 $4^7$
- 왜? 이모티콘의 할인율은 $4$개로 고정되어있다. $(10\%, 20\%, 30\%, 40\%)$
할인율이 결정된 후 이모티콘 플러스 서비스 가입자와 이모티콘 판매액 구하는데 $nm = 100 \times 7$
따라서 Backtracking $+$ Bruteforcing을 통해 구하면 된다.

오늘의 회고

Backtracking의 경계조건을 $n$으로 두어서 시간초과가 무한히 발생했다.
- $4^{100}$번 반복한 것..!
위의 오류를 해결하려고 미리 이모티콘의 할인율에 따라 테이블을 정해두려 했지만, 문제 특성상 그럴 수가 없었다.
경계조건을 $m$으로 두니 $3$개를 제외하고 틀렸다.
할인 받은 이모티콘을 구하는데 소수 계산을 통해서 했기 때문에 오차가 발생한 것이라고 예상하였고,
- 이모티콘의 가격이 $100$의 배수라는 점을 확인한 후 정수 연산으로 변경해주었다.
  - price $\div 100$은 price의 $1\%$이므로 여기에 할인율을 곱해주면 할인받는 가격을 구할 수 있다.
    - price는 $100$의 배수이기 때문에 $100$으로 나눈 몫만 구해주어도 $1\%$와 동일하다.
  - 이모티콘의 가격에서 위의 값을 빼주면 할인된 가격이다.
```
  discount_price = price // 100 * discount
  sum_of_buy += price - discount_price
```
  - 물론 price의 $1\%$에 $100 -$ 할인율을 곱해줘도 동일하다
```
  sum_of_buy += price // 100 * (100 - discount)
```

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]