[프로그래머스]150368: 이모티콘 할인 행사 | DFS

[프로그래머스]150368: 이모티콘 할인 행사- DFS

 

 

 

---

[python] 문제풀이

1 . DFS 사용하여 할인율 조합 생성

combo는 현재까지 선택된 이모티콘의 할인율 조합.

예를 들어, 첫 번째 이모티콘에 10% 할인을 선택했다면 combo에 [10]이 저장되고, 두 번째 이모티콘에 20% 할인을 선택했다면 combo가 [10, 20]으로 확장

 

2. 할입율 조합에 대한 구매 or 플러스 가입 계산

구매액 > 기준액 인 경우, 플러스 가입 (sub_count) 에 1을 더해줌

아닐 경, 구매액 (sales)에 1을 더해줌

 

2. 최대 가입자, 최대 판매 이익

sub_count > max_sub

 

• 현재 조합에서 서비스 가입자 수(sub_count)가 이전에 기록된 최대 가입자 수(max_sub)보다 많으면, 현재 조합이 더 나은 결과로 판단하고, max_sub와 max_sale을 업데이트
• 즉, 더 많은 가입자를 유치한 경우 더 좋은 할인율 조합이므로 이 조합의 결과를 저장

sub_count == max_sub and sales > max_sale

 

• 만약 현재 조합에서의 가입자 수(sub_count)가 기존 최댓값(max_sub)과 같다면, 이제 **매출(sales)**을 비교
• 매출이 더 크다면, 동일한 가입자 수에서 더 많은 매출을 올릴 수 있는 조합이므로 매출이 더 큰 조합을 선택

 

def solution(users, emoticons):
    # 가능한 할인율
    disc = [10, 20, 30, 40]
    max_sub = 0
    max_sale = 0

    # 모든 이모티콘에 대해 할인율 조합을 만드는 dfs 함수
    def dfs(depth, combo):
        nonlocal max_sub, max_sale
        
        if depth == len(emoticons):
            sub_count = 0
            sales = 0
            for rate, limit in users:
                total = 0
                for i, price in enumerate(emoticons):
                    if combo[i] >= rate:  # 할인율이 기준에 맞을 때만 구매
                        total += price * (100 - combo[i]) // 100
                if total >= limit:
                    sub_count += 1  # 이모티콘 플러스 서비스 가입
                else:
                    sales += total  # 구매한 금액 추가
            
            # 현재 조합이 가장 나은지 확인
            if sub_count > max_sub or (sub_count == max_sub and sales > max_sale):
                max_sub = sub_count
                max_sale = sales
            return

        # 이모티콘마다 할인율을 선택하여 dfs 호출
        for d in disc:
            dfs(depth + 1, combo + [d])

    # DFS 시작
    dfs(0, [])

    return [max_sub, max_sale]