https://school.programmers.co.kr/learn/courses/30/lessons/150368

---

1. 코드

def solution(users, emoticons):
    def dfs(idx, path):
        if idx == len(emoticons):
            cases.append(path)
            return
        for i in range(4):
            val = emoticons[idx] - (emoticons[idx] * d[i] * 0.01)
            dfs(idx + 1, path + [([d[i], int(val)])])


    answer = []
    cases = []
    d = {0: 10, 1: 20, 2: 30, 3: 40}
    dfs(0, [])


    for case in cases:
        buy, service = 0, 0

        for user_ratio, user_limit in users:
            user_buy = 0

            for i in range(len(case)):
                prd_ratio, prd_price = case[i]

                if prd_ratio >= user_ratio:
                    user_buy += prd_price

            if user_buy >= user_limit:
                service += 1
            else:
                buy += user_buy
                
        answer.append((service, buy))

    return list(sorted(answer, key=lambda x: (-x[0], -x[1]))[0])

---

2. 후기

1. 1 ≤ emoticons의 길이 = m ≤ 7
2. 1 ≤ users의 길이 = n ≤ 100
3. 행사 목적을 최대한으로 달성했을 때의...

위의 조건들을 보고 중복 순열을 사용해도 된다는 판단을 했다. 특히 3번 조건의 설명처럼 최대한 이라는 키워드를 보면 모든 경우를 탐색하는 편이 좋다.

본인은 중복순열 대신 dfs함수를 정의하여 모든 경우를 구했다. 중복순열을 사용한 풀이는 아래 코드를 참조

from itertools import product

emoticons = [1300, 1500, 1600, 4900]
percents = (10, 20, 30, 40)
prod = product(percents, repeat=len(emoticons))
print(list(prod))

# [(10, 10, 10, 10), (10, 10, 10, 20), 
# (10, 10, 10, 30) ...(40, 40, 40, 40)]