[Python] 예산

 

코딩테스트 연습 - 예산

처음 생각한 아이디어는 d에서 몇가지를 뽑아서 budget을 넘지 않으면서 가장 큰 값을 찾는 것을 생각했다.

하지만 그렇게 된다면 모든 경우의 수를 생각해야하고 로직이 복잡해질 것 같다는 생각을 했다.

그래서 생각한 아이디어는 다음과 같다.

 

1. d를 오름차순으로 정렬하여 작은 값부터 budget에서 빼나가면서 정답을 체크한다.

2. 정렬한 d의 첫 값이 budget보다 크면 지원할 부서는 없다.

 

def solution(d, budget):
	answer = 0
    d.sort()
    for i in range(len(d)):
    	if d[i] <= budget:
        	answer += 1
            budget -= d[i]
        else:
        	break
   	
    return answer