Algorithm/Programmers lv.1
[프로그래머스] 예산
채소기
2024. 8. 31. 22:15
https://school.programmers.co.kr/learn/courses/30/lessons/12982
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
전형적인 그리디(Greedy) 유형의 문제다. 우선 코드부터 올리도록 하겠다. ㅇㅅㅇ
def solution(d, budget):
d.sort()
total = 0
cnt = 0
for i in d:
if total + i <= budget:
total += i
cnt += 1
else:
break
return cnt
total = 예산을 지원한 총액
cnt = 예산을 지원받은 부서의 개수
이 문제의 핵심은 작은 금액을 요청한 부서부터 예산을 제공해주는 것이다. 따라서, 먼저 오름차순으로 정렬을 해주었다.
반복문을 통해 작은 금액 요청 부서부터 순서대로 예산을 제공해주고, 예산을 지원한 총액과 그 다음 부서가 요청한 금액의 합이 예산보다 크다면, 반목문을 종료한다.