[프로그래머스] 예산

https://school.programmers.co.kr/learn/courses/30/lessons/12982

프로그래머스

 

 

전형적인 그리디(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 = 예산을 지원받은 부서의 개수

 

이 문제의 핵심은 작은 금액을 요청한 부서부터 예산을 제공해주는 것이다. 따라서, 먼저 오름차순으로 정렬을 해주었다.

반복문을 통해 작은 금액 요청 부서부터 순서대로 예산을 제공해주고, 예산을 지원한 총액과 그 다음 부서가 요청한 금액의 합이 예산보다 크다면, 반목문을 종료한다.