문제 이해하기
inventory라는 배열이 주어져 있다고 가정해 봅시다. 여기서 inventory[i]는 처음에 보유하고 있는 i번째 색상 공의 개수를 나타냅니다. 그리고 고객이 구매하려는 공의 총 개수를 뜻하는 orders 값도 있습니다. 공은 어떤 순서로든 판매할 수 있으며, 고객은 어떤 색상의 공이든 상관없이 원합니다.
이 문제에서 공의 가치는 독특한 규칙을 따릅니다. 각 색상 공의 가치는 현재 재고에 남아 있는 해당 색상 공의 개수와 같습니다. 예를 들어 지금 파란 공이 6개 있다면, 첫 번째 파란 공은 가격 6에 판매됩니다. 이후 파란 공은 5개만 남으므로 다음 파란 공의 가치는 5가 됩니다. 목표는 orders개의 공을 판매한 후 얻을 수 있는 최대 총 가치를 구하는 것이며, 답이 너무 커질 경우 10^9 + 7로 나눈 나머지를 반환하면 됩니다.
입력 예시
예를 들어 inventory = [5, 7], orders = 6이라면 결과는 31이 됩니다. 첫 번째 색상의 공을 두 번 판매해 (5, 4)를 받고, 두 번째 색상의 공을 네 번 판매해 (7, 6, 5, 4)를 받으면 총 수익은 5 + 4 + 7 + 6 + 5 + 4 = 31이기 때문입니다.
풀이 접근법
이 문제는 이진 탐색(Binary Search)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 판매를 중단할 기준 가격, 즉 임계값(threshold)을 찾는 것입니다. 임계값보다 많은 공을 보유한 색상부터 우선적으로 판매하는 것이 항상 최적의 전략입니다.
다음 단계를 따릅니다 −
low := 0, high := 10000000으로 초기화합니다.
low < high인 동안 다음을 반복합니다.
mid := (low + high) / 2의 몫
s := 0
inventory의 각 요소 i에 대해, i > mid이면 s := s + (i - mid)
s > orders이면 low := mid + 1, 그렇지 않으면 high := mid
mid := (low + high) / 2의 몫
ans := 0
inventory의 각 요소 i에 대해, i > mid이면 다음을 수행합니다.
ans := ans + (i*(i+1)/2의 몫) - (mid*(mid+1)/2의 몫)
orders := orders - (i - mid)
ans := ans + orders * mid
ans mod (10^9 + 7)을 반환합니다.
알고리즘이 작동하는 이유
이진 탐색 단계에서는 특정 가격 mid까지 모든 공을 판매했을 때 필요한 판매량(s)이 orders 이하가 되는 최솟값을 찾습니다. 이후 mid보다 높은 가치를 지닌 공들을 모두 판매하고, 남은 주문 수만큼 가격 mid짜리 공을 추가로 판매하면 정확히 orders개를 판매하면서 총 수익이 최대화됩니다. 등차수열의 합 공식(i*(i+1)/2)을 활용하면 각 색상별 수익을 반복문 없이 한 번에 계산할 수 있습니다.
구현 예제
더 나은 이해를 위해 다음 구현을 살펴보겠습니다 −
def solve(inventory, orders):
low = 0
high = 10000000
while low < high:
mid = (low+high)//2
s = 0
for i in inventory:
if i > mid:
s += i-mid
if s > orders:
low = mid+1
else:
high = mid
mid = (low+high)//2
ans = 0
for i in inventory:
if i > mid:
ans += i*(i+1)//2 - mid*(mid+1)//2
orders -= i-mid
ans += orders*mid
return ans % (10**9 + 7)
inventory = [5,7]
orders = 6
print(solve(inventory, orders))
입력
[5,7], 6
출력
31
복잡도 분석
시간 복잡도는 이진 탐색의 반복 횟수 O(log M)(M은 최대 재고 값)과 매 반복마다 배열을 순회하는 비용 O(n)의 곱, 즉 O(n log M)입니다. 공간 복잡도는 추가 배열 없이 변수만 사용하므로 O(1)입니다.