문제 링크
문제 요약
문제에서의 가장 큰 목표는 2가지이고 순서대로 우선순위를 가지고 있다.
1 ) 이모티콘 플러스 서비스 가입자 최대
2 ) 이모티콘 판매액을 최대로
- 할인율은 [10, 20, 30, 40] 중 하나로 결정된다.
- 사용자들은 각자의 기준을 바탕으로 이모티콘을 구매하거나 이모티콘 플러스에 가입한다.
- 일정 비율 이상의 할인율은 모두 구매한다.
- 이모티콘 구매 비용의 합을 구했을 때 일정 가격이 넘어가면 구매했던 이모티콘을 모두 취소하고 이모티콘 플러스에 가입한다.
처음에 문제를 해결할 떄 바로 해결책이 생각나지 않아서 조금 헤맸었다.
무작정 그리디를 생각했지만, 마땅한 그리디 식 규칙성(?)이 보이지 않았다. 그래서 설마 전부 다 탐색해야하나 생각을 했었는데, 이모티콘 개수를 확인하고 완전 탐색 유형인가보다 하고 감을 잡았던 것 같다.
아래 해설 내용이 헷갈리면 주석 처리해둔 부분을 풀고 돌려보면 감이 잡힐 것이다!
문제 풀이
def solution(users, emoticons):
answer = [0, 0]
discount = [10, 20, 30, 40] # 할인율
emo_discount = []
# DFS 를 활용해서 모든 경우의 할인율 조합 구하기
def DFS(arr, d):
# arr는 이모티콘 별 할인율 조합
if d == len(arr):
emo_discount.append(arr[:]) # 얕은 복사
return
else:
for i in discount: # 할인율 for문 돌면서 재귀적으로 함수 호출
arr[d] +=i
#print(arr)
DFS(arr, d+1)
arr[d] = 0 # DFS 다 돌고나서 배열 원상 복구
# print(arr)
DFS([0]*len(emoticons), 0)
#print(emo_discount)
# 완전 탐색
for d in emo_discount:
regs = 0 # 가입자
prof = 0 # 수익
for user in users:
paid = 0
for i in range(len(d)):
if user[0] <= d[i]: # 일정 할인율 이상이라면
paid += emoticons[i] * (100-d[i]) / 100
if user[1] <= paid: # 일정 가격 이상이라면
paid = 0
regs += 1
prof += int(paid)
#print(regs, prof)
# 정답 결정 우선순위: 가입 여부 -> 버는 돈
if answer[0] <= regs:
if answer[0] == regs:
answer[1] = max(prof, answer[1])
else:
answer[0] = regs
answer[1] = prof
return answer
📌 해결 방법
완전탐색문제에 해당한다.- 완전 탐색을 위해서 할인율은 4가지로 정해져 있고, 이모티콘은 최대 7개이므로 모든 조합을
DFS를 활용해서 정리해준다.
