문제 요약
각 부서가 물품 구매에 필요한 금액을 신청했다.
전체 예산 budget 안에서 최대한 많은 부서를 지원해야 한다.
단, 한 부서를 지원하려면 해당 부서가 신청한 금액을 전부 지원해야 하며, 일부 금액만 지원할 수는 없다.
부서별 신청 금액 배열 d와 전체 예산 budget이 주어졌을 때, 지원 가능한 부서의 최대 개수를 구해야 한다.
핵심 아이디어
최대한 많은 부서를 지원하려면 신청 금액이 작은 부서부터 지원하는 것이 유리하다.
예산이 한정되어 있기 때문에 큰 금액을 먼저 지원하면 남은 예산으로 지원할 수 있는 부서 수가 줄어들 수 있다.
따라서 다음 순서로 해결한다.
- 신청 금액 배열
d를 오름차순 정렬한다. - 작은 금액부터 차례대로 예산에서 차감한다.
- 더 이상 지원할 수 없으면 종료한다.
이는 전형적인 그리디 문제다.
왜 그리디가 가능할까?
목표는 지원 금액의 합을 최소화하는 것이 아니라, 지원하는 부서의 개수를 최대화하는 것이다.
같은 1개 부서를 지원한다면 신청 금액이 작은 부서를 선택하는 것이 항상 유리하다.
작은 금액을 먼저 선택하면 남은 예산이 더 많아지고, 이후 더 많은 부서를 지원할 가능성이 커진다.
따라서 매 순간 가장 작은 신청 금액을 선택하는 전략이 최적해로 이어진다.
Python 코드
def solution(d, budget):
d.sort()
answer = 0
for cost in d:
if budget < cost:
break
budget -= cost
answer += 1
return answer코드 설명
신청 금액 정렬
d.sort()부서를 신청 금액이 작은 순서대로 정렬한다.
최대한 많은 부서를 지원해야 하므로 가장 적은 예산을 요구하는 부서부터 확인한다.
예산 확인
if budget < cost:
break현재 부서를 지원할 수 없다면 반복을 종료한다.
신청 금액이 오름차순으로 정렬되어 있으므로, 현재 부서를 지원할 수 없다면 뒤에 있는 부서들도 지원할 수 없다.
예산 차감과 개수 증가
budget -= cost
answer += 1현재 부서를 지원할 수 있다면 예산에서 신청 금액을 빼고, 지원한 부서 수를 1 증가시킨다.
시간 복잡도
부서 신청 금액을 정렬하는 데 가장 많은 시간이 걸린다.
부서 수를 n이라고 하면 시간 복잡도는 다음과 같다.
O(n log n)정렬 이후에는 배열을 한 번 순회하므로 O(n)이다.
공간 복잡도
입력 배열을 직접 정렬하고, 추가로 큰 자료구조를 사용하지 않는다.
O(1)단, Python의 정렬 내부 구현에 따른 추가 공간은 별도로 사용될 수 있다.
정리
이 문제는 최대한 많은 부서를 지원해야 하므로 작은 신청 금액부터 선택하는 것이 핵심이다.
정렬 후 예산이 허용하는 만큼 차례대로 지원하면 된다.
작은 금액부터 지원한다.
지원 가능하면 예산에서 차감한다.
지원 불가능하면 종료한다.간단하지만 그리디의 기본 원리를 잘 보여주는 문제다.
