문제 개요
어느 사탕 가게에서 N가지 서로 다른 종류의 사탕을 판매하고 있으며, 각 사탕의 가격이 주어져 있다고 가정해 보겠습니다. 이 가게는 매력적인 프로모션을 진행 중인데, 사탕 하나를 구매하면 다른 종류의 사탕을 최대 K개까지 무료로 받을 수 있습니다.
우리의 목표는 두 가지입니다.
- N가지 사탕을 모두 구매하기 위해 지불해야 하는 최소 금액 구하기
- N가지 사탕을 모두 구매하기 위해 지불해야 하는 최대 금액 구하기
두 경우 모두 프로모션을 최대한 활용하여 무료로 얻을 수 있는 사탕을 최대한 많이 받아야 합니다. 구매 시점에 남아 있는 사탕이 k개 이상이라면 매 구매마다 정확히 k개를 무료로 선택해야 하고, k개보다 적다면 남은 사탕 전부를 무료로 가져가야 합니다.
입력 예시와 결과 분석
예를 들어 price = [4, 3, 2, 5]이고 k = 2라고 가정해 봅시다. 이때 출력은 최솟값 = 5, 최댓값 = 9가 됩니다.
k가 2이므로 사탕 하나를 구매할 때마다 두 개까지 무료로 가져갈 수 있습니다. 먼저 최소 비용의 경우를 살펴보겠습니다. 가장 저렴한 2원짜리 사탕을 구매하고 가격이 4와 5인 사탕을 무료로 가져간 뒤, 3원짜리 사탕만 추가로 구매하면 됩니다. 따라서 최소 비용은 2 + 3 = 5입니다.
반대로 최대 비용의 경우에는 가장 비싼 사탕부터 구매합니다. 5원짜리 사탕을 구매하고 가격이 2와 3인 사탕을 무료로 가져간 후, 4원짜리 사탕을 추가로 구매하면 됩니다. 따라서 최대 비용은 4 + 5 = 9입니다.
풀이 접근 방식
이 문제는 그리디(Greedy) 알고리즘으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 최소 비용: 가장 싼 사탕부터 구매하면, 구매할 때마다 상대적으로 비싼 사탕들이 무료로 처리되므로 총비용이 줄어듭니다.
- 최대 비용: 가장 비싼 사탕부터 구매하면, 값싼 사탕들이 무료로 처리되므로 총비용이 늘어납니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- get_min() 함수를 정의합니다. 인자는 가격 리스트 A와 k입니다.
- n := 리스트 A의 크기로 설정합니다.
- 리스트 A를 오름차순으로 정렬합니다.
- res := 0, i := 0으로 초기화합니다.
- n이 0이 아닌 동안 다음을 반복합니다.
- res := res + A[i]
- n := n - k
- i := i + 1
- res를 반환합니다.
- get_max() 함수를 정의합니다. 마찬가지로 A와 k를 인자로 받습니다.
- n := 리스트 A의 크기로 설정하고, A를 오름차순으로 정렬합니다.
- res := 0, idx := 0, i := n-1로 초기화합니다.
- i >= idx인 동안 다음을 반복합니다.
- res := res + A[i]
- idx := idx + k
- i := i - 1
- res를 반환합니다.
- 메인 부분에서 get_min(A, k)와 get_max(A, k)를 호출하여 결과를 구합니다.
구현 예제
아래 파이썬 구현을 통해 더 자세히 이해해 보겠습니다.
def get_min(A,k):
n = len(A)
A.sort()
res = 0
i=0
while(n):
res += A[i]
n = n-k
i += 1
return res
def get_max(A, k):
n = len(A)
A.sort()
res = 0
idx = 0
i=n-1
while(i>=idx):
res += A[i]
idx += k
i -= 1
return res
A = [4, 3, 2, 5]
k = 2
print(get_min(A, k), get_max(A, k))입력
[4, 3, 2, 5], 2
출력
5 9
복잡도 및 정리
두 함수 모두 리스트 정렬이 지배적인 연산이므로 시간 복잡도는 O(n log n)입니다. 정렬 이후의 반복문은 O(n)으로 선형 시간에 처리됩니다.
정리하자면, 최소 금액을 구할 때는 오름차순 정렬된 리스트의 앞쪽에서 사탕을 구매하고, 최대 금액을 구할 때는 내림차순 순서(뒤쪽)에서 사탕을 구매하며, 매 구매마다 k개씩 무료로 가져가는 것이 이 문제의 핵심 전략입니다.