https://school.programmers.co.kr/learn/courses/30/lessons/150368
문제 파악
카카오톡에서 이모티콘 할인행사를 한다.
우선순위 1. 이모티콘 플러스 서비스 가입자를 최대한 늘린다.
우선순위 2. 이모티콘 판매액을 최대한 늘린다.
n명의 카카오톡 사용자들에게 이모티콘 m개를 할인하여 판매한다.
이모티콘 할인율은 10%,20%,30%,40% 중 하나로 설정된다.
카카오톡 사용자들은 1. 이모티콘을 사거나, 2. 임티 플러스 서비스에 가입한다.
- 각 사용자들은 자신의 기준에 따라 일정 비융 이상 할인하는 이모티콘을 모두 구매한다.
- 각 사용자들은 자신의 기준에 따라 이모티콘 구매 비용의 합이 일정 가격 이상이 된다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입한다.
사용자 1은 이모티콘이 40%이상 할인을 하면 어떤 이모티콘이라도 다 산다.
그런데 가격이 10,000원이 넘어가면 다 취소하고 플러스 서비스에 가입한다.
사용자 2는 25%이상 할인하면 다 사고,
10,000원이 넘어가면 다 취소하고 플러스 서비스에 가입한다.
밑에는 이모티콘 종류와 가격이 주어져있다.
7,000원, 9,000원 짜리 이모티콘 두개다 40% 씩 할인하면
1,2번 사용자 모두 구매하게 되고, 9,600원을 사용한다.
10,000원을 안넘어가니 플러스 서비스는 가입하지 않는다.
하지만 할인율은 30%,40% 이렇게 할인하면 결과는 다르다.
이처럼 사용자 수 n 구매 기준을 담은 2차원 정수배열 users , 이모티콘 개수 m, 정가를 담은 1차원 정수배열 emoticons가 주어졌을 때,
행사 목적(1.최대 가입자 수, 2.최대 판매액)을 최대한으로 달성했을 때의 이모티콘 플러스 서비스 가입 수와 이모티콘 매출액을 1차원 정수 배열에 담아 return 하도록 해야한다.
유저 수 100 이하
할인율 40% 이하
이모티콘 개수 7 이하
정가 1,000,000원 이하
할인율은 10,20,30,40 중 하나라는 점이 있어서 문제가 그나마 풀만해 보인다.
우리가 해야하는 것은 이모티콘 별 할인율을 적절하게 책정해서,
1. 더 많은 유저들의 가격 마지노선을 넘겨 플러스 이모티콘 서비스의 가입하게 하는 것
2. 그것이 안된다면, 제일 비싸게 파는 것
이모티콘별 할인율의 가짓수는 4이다.
최대 이모티콘의 수는 7이다.
그렇다면 할인율이 책정되는 최대 경우의 수는
4의 7승 = 2의 14승 = 2의 10승 x 2의 4승 = 1024 x 16,
약 16,000이다.
최대 유저 수가 100이기에 16,000에 100을 곱해도 백 육십만,
완전 탐색이 가능해보인다.
해답 및 풀이
def solution(users,emoticons):
"""
전체 흐름 요약
1) 각 이모티콘에 대해 [10,20,30,40]% 할인 시 가격을 미리 계산한다. -> discounted_emoticons
2) DFS로 이모티콘별 할인율 인덱스(plan)를 0..3 중 하나로 전부 배치(= 4^m 경우)한다.
3) 하나의 plan이 완성될 때마다 evaluate()로 (플러스 가입자 수, 매출)을 계산한다.
4) (가입자 수 최대) → 동률이면 (매출 최대) 기준으로 최적값을 갱신한다.
"""
# 모든 emoticons 들에 대해 할인율(DISCOUNT_RATE)을 적용한 리스트 만들기
DISCOUNT_RATE = [10,20,30,40] # 할인율
discounted_emoticons = [] # discounted_emoticons[i][k] = i번째 이모티콘을, DISCOUNT_RATE[k]% 로 깎았을 때의 가격
for emoticon_price in emoticons:
row = []
for d in DISCOUNT_RATE:
new_price = emoticon_price * (100 - d) // 100
row.append(new_price)
discounted_emoticons.append(row) #[[6300, 5600, 4900, 4200], [8100, 7200, 6300, 5400]]
# ---
plan = [0] * len(emoticons)
def evaluate():
"""
[평가 함수 - DFS로 하나의 plan이 완성될 때 호출]
- 현재 plan에 적힌 할인 인덱스(0..3)에 따라 각 유저의 구매/가입 결과를 합산한다.
- 규칙:
* 유저는 자신의 최소 할인율(min_discount) 이상으로 할인된 이모티콘만 구매 대상에 포함한다.
* 그 합계가 유저의 한도(limit) 이상이면 즉시 "플러스 가입" 처리(= 매출 0), 해당 유저 계산 종료.
* 한도 미만이면 누적 합을 매출로 더한다.
- 반환: (subs, revenue)
subs: 이번 plan에서의 총 플러스 가입자 수
revenue: 이번 plan에서의 총 매출
"""
subs = 0
revenue = 0
for min_discount, limit in users: # 유저에 대해
total = 0 # 한 유저의 구매 총액
for i in range(len(discounted_emoticons)): # 할인된 이모티콘을 돌며
# 할인율이 유저의 min_discount 보다 크거나 같으면 산다.
if DISCOUNT_RATE[plan[i]] >= min_discount:
total += discounted_emoticons[i][plan[i]] # 총액 추가
# 총액이 limit를 넘어가는 순간 플러스 가입시키고 break
if total >= limit:
subs += 1 # 가입자 1추가
total = 0 # total 리셋 시켜주고
break
revenue += total # limit를 넘지 않아 서비스에 가입하지 않았다면 한 유저의 구매액 total을 총 매출 revenue 에 반영
return subs,revenue
def dfs(idx):
"""
[DFS - 완전탐색]
- idx번째 이모티콘에 대해 가능한 4가지 할인 인덱스(0..3)를 배치하고,
다음 이모티콘으로 넘어간다.
- 종료 조건(idx == m): 즉, 모든 이모티콘의 할인 인덱스를 정한 시점.
-> evaluate()를 호출하여 (가입자, 매출)을 얻고, 최적해를 갱신한다.
동작 흐름(예: m=3):
dfs(0)
plan[0]=0 → dfs(1)
plan[1]=0 → dfs(2)
plan[2]=0 → evaluate() # [0,0,0]
plan[2]=1 → evaluate() # [0,0,1]
plan[2]=2 → evaluate() # [0,0,2]
plan[2]=3 → evaluate() # [0,0,3]
plan[1]=1 → dfs(2) ... # [0,1,*]
plan[1]=2 → dfs(2) ...
plan[1]=3 → dfs(2) ...
plan[0]=1 → dfs(1) ...
plan[0]=2 → dfs(1) ...
plan[0]=3 → dfs(1) ...
"""
if idx == len(emoticons):
return evaluate()
best_subs = 0
best_revenue = 0
for k in range(4):
plan[idx] = k
subs, rev = dfs(idx + 1)
# 현재까지의 최고값 갱신
if subs > best_subs or (subs == best_subs and rev > best_revenue):
best_subs, best_revenue = subs, rev
return best_subs, best_revenue
return list(dfs(0)) 예제 흐름
users = [[40,10000], [25, 10000]]
emoticons = [7000, 9000]
dfs(0)
├ plan[0]=0 → dfs(1)
│ ├ plan[1]=0 → dfs(2) → evaluate([0,0])
│ ├ plan[1]=1 → dfs(2) → evaluate([0,1])
│ ├ plan[1]=2 → dfs(2) → evaluate([0,2])
│ └ plan[1]=3 → dfs(2) → evaluate([0,3])
├ plan[0]=1 → dfs(1)
│ ├ plan[1]=0 → dfs(2) → evaluate([1,0])
│ ├ plan[1]=1 → dfs(2) → evaluate([1,1])
│ ├ plan[1]=2 → dfs(2) → evaluate([1,2])
│ └ plan[1]=3 → dfs(2) → evaluate([1,3])
├ plan[0]=2 → dfs(1) → ... (evaluate([2,0])~[2,3])
└ plan[0]=3 → dfs(1) → ... (evaluate([3,0])~[3,3])흐름 단계별 이모티콘의 개수 2개 일때
- dfs(0) 호출
idx=0: 첫 번째 이모티콘 할인율을 정하는 단계.
for k in [0,1,2,3]
→ 첫 번째 이모티콘을 10%,20%,30%,40% 중 하나로 정함.
- dfs(1) 호출
idx=1: 두 번째 이모티콘 할인율을 정하는 단계.
위에서 첫 번째 할인율을 정했으니,
이제 두 번째 할인율을 하나씩 정해봄.
- dfs(2) 호출
idx=2 == m → 이모티콘 2개를 다 정한 상태!
→ 이제 evaluate() 실행.
→ (subs, revenue) 결과 계산 후 리턴.
plan은
[0,0]
[0,1]
[0,2]
[0,3]
[1,0]
[1,1]
[1,2]
[1,3]
[2,0]
[2,1]
[2,2]
[2,3]
[3,0]
[3,1]
[3,2]
[3,3]흐름으로 dfs에서 커져가며 eval에서 평가된다.
재귀에 익숙해질 필요가 있다.
