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

이모티콘 할인행사를 하는데, 사람들이 자기가 정한 비율 이상으로 할인하는 이모티콘만 구매하려고 하고 만약 구매하는 총합이 자기 기준의 이상이면 임티플로 넘어간다고 한다.

여러 이모티콘이 주어지고 그럴 때 임티플 가입자 최대, 그리고 판매비용 최대인 경우 가입자 수와 판매 금액을 구하는 문제이다.

문제를 제대로 안 읽고 할인 비율이 0~40까지 정수인줄 알고 최악의 경우가 40 ** 7을 포함하겠구나 싶었는데 할인 비율이 10, 20, 30, 40으로 정해져 있어서 그냥 완전탐색으로 방향을 정했다.

Python

def solution(users, emoticons):
    answer = []
    
    sold = [0] * len(users) + [0] # 유저들에게 판 금액 + 임티플 가입자수
    ans = []
    dfs(0, sold, users, emoticons, ans)
    
    ans.sort(reverse=True) 
    
    return [ans[0][0], int(ans[0][1])]

def dfs(start, sold, users, emoticons, ans):
    
    if start == len(emoticons):
        for idx in range(len(sold)-1):
            if users[idx][1] <= sold[idx]:
                sold[-1] += 1
                sold[idx] = 0
        ans.append([sold[-1], sum(sold[:-1])])
    else:
        for d in [10, 20, 30, 40]:
            tmp = sold[:]
            for idx, u in enumerate(users):
                if u[0] <= d:
                    tmp[idx] += emoticons[start] * (100 - d) / 100
            
            dfs(start + 1, tmp, users, emoticons, ans)

먼저 판매량을 저장할 리스트를 만들었다. 고객 수 + 1의 길이로 정했는데, 마지막 칸은 임티플 가입자수 판단을 위해서 적었다.

DFS로 탐색하면서 else에서는 현재 start 이모티콘에 대해서 10~40의 할인 비율을 적용하는데, 할인 비율이 고객 마음에 들면 sold에 할인한 금액을 더해주었다. 그리고 start+1로 다음 이모티콘에 대해서 탐색이 되도록 했다.

만약 모든 이모티콘에 대한 탐색을 마쳤다면 판매금액을 돌면서 만약 고객이 임티플로 넘어갈 금액이라면 가입자 수에 1을 더하고, 해당 고객은 아무것도 구매하지 않는 것으로 처리했다.

그렇게 정리가 끝나면 ans리스트에는 임티플 가입자 수와 나머지 판매금액을 더해주었다.

마지막으로 ans를 내림차순으로 정렬하여서 첫번째 나오는 경우에 대해서 정수처리해서 출력했다.

문제를 대충 풀어서 그런가 굳이 sold에 임티플 가입자수가 없어도 될 것 같은데 들어갔고, sum(sold[:-1])할 때 정수처리 같이해줘도 되는데 굳이 맨 마지막에 했다. 성능에 크게 영향을 미치지 않고, 정답도 통과한 코드이지만 조금 더 들여다보고 더 최적화할 수 있는 것은 해야겠다.