[Level 2 | Python] 이모티콘 할인행사 (2023 KAKAO BLIND RECRUITMENT)

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

프로그래머스

문제

카카오톡에서 이모티콘 할인 행사를 한다. 목표는 다음과 같다.

1. 이모티콘 플러스 서비스 가입자를 최대한 늘리기

2. 이모티콘 판매액을 최대한 늘리기 (이모티컨 플러스 서비스 가입자가 같다면)

 

여기서 중요한 점은 이모티콘 할인행사의 할인율은 이모티콘마다 다를 수 있고, 10%, 20%, 30%, 40% 중에 하나이다.

 

풀이 과정

처음에 딱 보고 완전탐색으로 풀 수 있나 시간복잡도를 계산해보았다. 

시간복잡도
사용자 수 최대 100명, 이모티컨 개수 최대 7개, 할인율(10%,20%,30%,40%)은 최대 4개이다.
100*7*(4^7) = 11,468,800 
완전탐색으로 풀 수 있다! 

 

dfs를 이용한다. 기저조건은 depth가 이모티콘 총 개수와 같아질 때이다. 

discount의 할인율 4개를 리스트(10%,20%,30%,40% 할인율 적용)로 만들고 4가지를 모든 조합의 경우마다 구한다.

이모티콘[0] 가 10%를 선택할 경우, 20% 선택할 경우, 30% 선택할 경우, 40% 선택할 경우
이모티콘[1] 가 10%를 선택할 경우, 20% 선택할 경우, 30% 선택할 경우, 40% 선택할 경우
....
이모티콘[m] 가 10%를 선택할 경우, 20% 선택할 경우, 30% 선택할 경우, 40% 선택할 경우

 

이모티콘을 구매할지 말지 정하고 구매한다면 tmp_sum에 더해준다.

tmp_sum이 이모티콘 플러스를 구매해야 하는 금액 이상이 되면 이모티콘 플러스를 구매한 인원의 변수 plus에 +1을 해준다. 아니면 total_sum에 tmp_sum을 더해준다. 

 

기존 플러스 구입 고객보다 많은 경우가 있다면 answer을 갱신해준다(위에 1번 목표). 기존 플러그 구입 고객과 같은데 total_sum이 큰 경우에도 갱신해준다. (위에 2번 목표)

def solution(users, emoticons):
    n,m=len(users),len(emoticons)
    discount=[0.9,0.8,0.7,0.6]
    answer = [0,0]
    def dfs(depth,tmp):
        if depth==m:
            plus=0
            total_sum=0
            for user_rate, plus_price in users:
                tmp_sum=0
                for emo_rate, emo_price in tmp:
                    if user_rate<=emo_rate:
                        tmp_sum+=emo_price                      
                flag = tmp_sum // plus_price
                if flag:
                    plus+=1
                else:
                    total_sum += tmp_sum
            if answer[0]<plus:
                answer[0] = plus
                answer[1] = total_sum
            elif answer[0]==plus and answer[1] < total_sum:
                answer[1]=total_sum
            return
            
        for i in range(4):
            dfs(depth+1,tmp+[[100-discount[i]*100, emoticons[depth]*discount[i]]])

    
    dfs(0,[])
    return answer