문제
https://school.programmers.co.kr/learn/courses/30/lessons/150368
- n: 카카오톡 사용자 수
- m: 이모티콘 개수
- 이모티콘 할인율은 10%, 20%, 30%, 40% 중 하나로 설정
- 사용자는 자신이 정한 비율 이상의 할인율일 경우 이모티콘을 구매
- 사용자는 이모티콘 총 구매 비용이 자신이 정한 금액 이상일 경우, 구매를 모두 취소하고 이모티콘 플러스 가입
풀이
1<=n<=100, 1<=m<=7 조건으로 매우 널널하다.
모든 할인율 조합을 찾아 처리해도 충분하다.
- emoticon_discount[i] (1<=i<=7) : 각 이모티콘에 적용할 할인율을 저장하는 리스트
- discountList={10,20,30,40} : 적용할 할인율
- result_count: 최종 플러스 가입자수
- result_amount: 최종 판매 금액
emoticon_discount의 길이가 m일 경우 == 스택이 다 찬 경우
-
해당 할인율 조합에 대해 이모티콘 가격 계산
- plus_count: 현재 할인율 조합에서 플러스 가입자 수
- total_amount: 현재 할인율 조합에서 누적 판매액
-
1-N번째 유저의 조건들과 비교하여 가입자수/이익 계산
- 이모티콘 할인율이 유저의 기준 비율보다 크면 구매
- 유저의 누적 구매비용이 유저의 기준 금액보다 커지는 순간 플러스 가입자 수 증가
- 해당 유저가 플러스 가입자가 아닐 경우 구매 금액을 total_amount에 더함
-
result_count, result_amount 와 비교 및 업데이트
- plus_count > result_count,
=> result_count, result_amount 업데이트 - plus_count == result_count && total_amount > result_amount
=> result_amount 업데이트
- plus_count > result_count,
emoticon_discount 길이 != m
- discount[i]를 emoticons_discount에 push한 후 재귀호출
- 호출이 끝나면 push한 값을 pop
코드
https://github.com/LGY010011/Algorithm/blob/main/Algorithm/P150368.cpp
