[Lv.2] 이모티콘 할인행사

프로그래머스

 

1. 문제

목표

- 이모티콘 플러스 서비스 가입자를 최대한 늘리는 것

- 이모티콘 판매액을 최대한 늘리는 것

 

1번 목표가 우선이며, 2번 목표가 그 다음입니다.

 

각 사용자들은 자신의 기준에 따라 일정 비율 이상 할인하는 이모티콘을 모두 구매합니다.

각 사용자들은 자신의 기준에 따라 이모티콘 구매 비용의 합이 일정 가격 이상이 된다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입합니다.

 

[입력]

- n: 카카오톡 사용자 수

- users: 구매 기준 배열

- m: 이모티콘 개수

- emoticons: 이모티콘의 정가 배열

 

행사 목적을 최대한으로 달성했을 때의 이모티콘 플러스 서비스 가입 수와 이모티콘 매출액을 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요.

 

2. 제한사항

2.1 users

- 1 <= users의 길이 = n <= 100

- [ 비율, 가격 ]

 

2.2 emoticons

- 1 <= emoticons의 길이 = m <= 7

 

3. 풀이

어떻게 풀까 고민을 하다 답이 안나와서 완전탐색으로 풀려고 합니다.

각 emoticon에 적용할 수 있는 할인 비율이 0%, 10%, 20%, 30%, 40% 딱 5가지 입니다.

 

emoticon의 개수가 많아도 7개이므로, 흠.. 5의 7승(=78,125) 밖에 되지 않기 때문입니다. 😆👍🏻

 

그럼 각 경우의 수를 어떻게 둘까요? 저는 재귀함수를 사용하였습니다.

# 할인 비율
RATE = [10,20,30,40]

# index: 현재 emoticon의 index
# total: total[i]는 i번째 사용자가 구입한 emoticon의 총 가격
# users, emoticon: solution 매개변수로 전달된 users와 emoticons
def solve(index, total, users, emoticons):
	if index == len(emoticons):
    	return
    
    # index번째 emoticon을 r만큼 할인
    for r in RATE:
    	# 할인된 가격
        dp = int(emoticons[index] * (100-r) / 100)
        
        # 각 사용자들의 기준 이상으로 할인하는 경우에만 구입
        for i, (ru, rp) in enumerate(users):
        	if ru <= r:
            	total[i] += dp
        
        solve(index+1, total, users, emoticons)
        
        # 구입했던 가격을 다시 빼주는 추가 작업이 필요
        for i, (ru, rp) in enumerate(users):
        	if ru <= r:
            	total[i] -= dp

 

4. 코드

RATE = [10,20,30,40]
a_total = 0
a_member = 0

def solution(users, emoticons):
    answer = []
    
    solve(0, [0]*len(users), users, emoticons)
    return [a_member, a_total]

def solve(index, total, users, emoticons):
    global a_total, a_member
    if index == len(emoticons):
        n_total, member = 0, 0
        for i, count in enumerate(total):
            # 가격 이상의 돈을 이모티콘 구매에 사용
            if count >= users[i][1]:
                member += 1
            else:
                n_total += count
        
        if a_member < member:
            a_total = n_total
            a_member = member
        elif a_member == member and a_total < n_total:
            a_total = n_total
            a_member = member
        return
    
    # index번째 emoticon을 r만큼 할인
    for r in RATE:
        dp = int(emoticons[index] * (100-r) / 100)
        for i, (ru, rp) in enumerate(users):
            if ru <= r:
                total[i] += dp
                
        solve(index+1, total, users, emoticons)
        
        for i, (ru, rp) in enumerate(users):
            if ru <= r:
                total[i] -= dp