이번 이슈는 이모티콘 할인 이벤트 이슈입니다.
문제의 핵심은 이모티콘 플러스 서비스 가입자를 최대한 늘리면서 이모티콘 판매를 최대한 늘리는 것이다.
먼저 용어를 살펴보겠습니다.
판매 이모티콘의 할인율은 10%, 20%, 30%, 40%로 고정되어 있습니다.
사용자마다 기준은 다르지만 모든 이모티콘을 일정 비율 이상 할인된 가격으로 구매한다.
이때 이모티콘 구매 비용의 합이 일정 금액 이상일 경우 사용자는 모든 구매내역을 취소하고 이모티콘 플러스 서비스에 가입하게 됩니다.
위 예시처럼 사용자가 2명이고 40%, 25% 할인이 적용되면 이모티콘을 구매합니다. 또한 이모티콘 플러스 서비스 가입 기준은 둘 다 1만원이다.
먼저 두 이모티콘을 40% 할인하면 두 이모티콘 모두 판매가 가능하지만 서비스 가입자는 0명이고 당시 판매 금액은 19,200원이다.
1번 이모티콘을 30% 할인하고 2번 이모티콘을 $40 할인하면 사용자 1번은 2번만 구매하고, 사용자 2번은 1번과 2번을 모두 구매하게 됩니다. 사용자 2의 누적 구매 비용 1만원은 초과하면 사용자의 모든 구매가 취소되고 사용자는 이모티콘 플러스 서비스에 가입합니다. 즉, 서비스 가입자의 경우 판매 금액은 5,400원입니다.
위의 표에서 알 수 있듯이 두 제품을 모두 30% 할인할 경우 User 2의 누적 구매 금액은 11,200원입니다. 따라서 서비스 가입은 가능하나, 이때는 구매한 상품이 없으므로 판매금액은 0원입니다.
따라서 문제에서 가장 먼저 살펴봐야 할 것은 서비스 가입 기준 바로 위의 할인율이다.
할인율을 찾기 위해 itertools 라이브러리를 사용했습니다.
먼저 판매 기본값인 Sale을 선언하고, product()를 사용하여 이모티콘 길이까지 중복 요소를 허용하는 방식으로 판매를 결합했습니다.
이제 사용자가 루프를 통과함에 따라 빗을 적용하여 누적 금액이 계산됩니다.
최종 적립 및 구매 금액을 서비스 가입 기준과 비교하여 가입 기준을 만족하면 join_pay(0)의 값을 1 증가시키고 그렇지 않으면 누계 금액을 join_pay(1)에 더합니다.
이 방법이 통하는 이유는 이모티콘의 최대 개수가 7개이기 때문입니다. 4가지 할인율에 7을 곱해도 16384건이 발생하기 때문에 타임아웃의 위험이 없다.
