과일 목록 fruits와 두 개의 값 k, cap이 주어졌다고 가정해 보겠습니다. 각 fruits[i]는 [c, s, t] 형태의 세 값을 가지며, 여기서 c는 해당 과일의 개당 가격, s는 개당 크기, t는 총 수량을 의미합니다. 또한 k는 용량이 cap인 과일 바구니의 개수입니다.
문제 설명 및 제약 조건
바구니를 채울 때는 아래 제약 조건을 순서대로 지켜야 합니다.
- 각 바구니에는 한 가지 종류의 과일만 담을 수 있습니다.
- 각 바구니는 최대한 꽉 차도록 채워야 합니다.
- 각 바구니는 최대한 저렴하게 채워야 합니다.
즉, 이 문제의 목표는 최대한 많은 바구니를 채우는 데 필요한 최소 비용을 구하는 것입니다.
예를 들어 입력이 fruits = [[5, 2, 3], [6, 3, 2], [2, 3, 2]], k = 2, cap = 4라고 해보겠습니다. 이때 출력은 12가 됩니다. 첫 번째 바구니에는 0번 과일 두 개(크기 2 + 2 = 4)를 담아 완전히 채울 수 있으며, 비용은 5 + 5 = 10입니다. 두 번째 바구니는 더 저렴한 2번 과일 하나로 채우면 되므로 비용은 2입니다. 따라서 총 비용은 10 + 2 = 12입니다.
해결 접근 방식
이 문제는 그리디(Greedy) 알고리즘으로 효율적으로 해결할 수 있습니다. 전체 흐름은 다음과 같습니다.
- 옵션 생성: 새 리스트
options를 만듭니다. fruits의 각 (c, s, t) 조합에 대해 t > 0인 동안 다음을 반복합니다.fnum = min(cap // s, t): 한 바구니에 담을 수 있는 과일 수를 계산합니다.- fnum이 0이면(과일 크기가 바구니 용량보다 커서 담을 수 없는 경우) 반복을 중단합니다.
bnum = t // fnum: fnum개씩 담을 수 있는 바구니의 개수를 구합니다.- (남은 용량, 바구니당 비용, 바구니 수)에 해당하는 튜플
(cap - fnum * s, fnum * c, bnum)을 options 끝에 추가합니다. - t에서
bnum * fnum을 빼고 남은 수량으로 위 과정을 반복하면, 덜 찬 바구니 옵션들도 자동으로 생성됩니다.
- 정렬: options를 오름차순으로 정렬합니다. 파이썬 튜플 정렬 특성상 남은 용량(left_cap)이 작은 순서, 즉 더 꽉 찬 바구니가 먼저 오고, 남은 용량이 같다면 비용이 낮은 옵션이 앞에 위치합니다. 이는 '꽉 참 우선, 그다음 저렴함'이라는 제약 조건의 우선순위와 정확히 일치합니다.
- 비용 계산: 정렬된 옵션을 순회하면서
bfill = min(k, bnum)만큼 바구니를 채우고,ans에bcost * bfill을 누적합니다. k가 0이 되면 반복을 종료합니다. - 최종적으로
ans를 반환합니다.
이 방식의 시간 복잡도는 옵션 정렬이 지배하므로 O(n log n)으로 매우 효율적입니다.
구현 코드
이해를 돕기 위해 다음 파이썬 구현을 살펴보겠습니다.
def solve(fruits, k, cap):
options = []
for c, s, t in fruits:
while t > 0:
fnum = min(cap // s, t)
if fnum == 0:
break
bnum = t // fnum
options.append((cap - fnum * s, fnum * c, bnum))
t -= bnum * fnum
ans = 0
for left_cap, bcost, bnum in sorted(options):
bfill = min(k, bnum)
ans += bcost * bfill
k -= bfill
if k == 0:
break
return ans
fruits = [[5, 2, 3],[6, 3, 2],[2, 3, 2]]
k = 2
cap = 4
print(solve(fruits, k, cap))
입력
[[5, 2, 3],[6, 3, 2],[2, 3, 2]], 2, 4
출력
12