프로그래머스) 이모티콘 할인행사(python)

문제

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

프로그래머스

 

나의 풀이

def solution(users, emoticons):
    answer = [0, 0]
    data = [10, 20, 30, 40]
    
    discount = []
    def dfs(L,tmp):
        if L == len(tmp):
            discount.append(tmp[:])
            return
        else:
            for i in data:
                tmp[L]+=i
                dfs(L+1,tmp)
                tmp[L]-=i
    dfs(0,[0]*len(emoticons))
    
    for dis in discount:
        cnt = 0
        get = 0
        for u in users:
            pay = 0
            for j in range(len(dis)):
                if u[0] <= dis[j]:
                    pay += emoticons[j]*(100-dis[j])/100
            if pay >= u[1]:
                pay = 0
                cnt += 1
            get += pay
        if cnt >= answer[0]:
            if answer[0] == cnt:
                answer[1] = max(answer[1], get)
            else:
                answer[1] = get
            answer[0] = cnt
        
    
    return answer

 

풀이 해설

 

이 문제를 풀면서 할인비율을 얼마로 측정해야할지 고민이 많았고, 우선순위로 어떤값을 뽑아야하는지 고민이 많았다.

 

1. 이모티콘 할인비율을 DFS로 조합을 이룬다

2. 조합비율을 기준으로, 유저별로 완전탐색을 진행한다

3. 유저의 할인비율을 비교

- 할인비율을 충족하지만, 내 금액을 넘으면 이모티콘 구매 변수를 늘린다

- 아니라면, 구매 금액에 추가한다

4. 이후, answer의 값의 우선순위별로 비교해서 값을 갱신한다.

 

회고

완전탐색이면서 조합을 만드는데 dfs를 사용하는 방법을 배울 수 있었다.