24. 예산 ★ (그리디;;)

유형 : 그리디....

나는 그리디가 싫다.,........

 

1. recursion 

def solution(d, budget):
    answer = buy(d, budget, 0)
    return answer

def buy(d, n, finish):
    if n == 0 or not d:
        return finish
    res = []
    for i in range(len(d)):
        if d[i] > n:
            return finish
        new = d.copy()
        curr = new.pop(i)
        res.append(buy(new, n-curr, finish + 1))
    return max(res)

 

결과 : 시간 초과 

recursion으로 푸는 게 아니었다.

뭔가 이게 아니다 싶으면 빨리 다른 알고리즘을 생각해보자. 

 

2. greedy 

 그냥 제일 작은 부서부터 빼면 그게 최대 부서의 숫자가 되는거였다. 당연함. 

def solution(d, budget):
    d.sort()
    ans = 0
    for money in d:
        if money > budget:
            return ans
        budget -= money
        ans += 1
    return ans

 

ㅎㅎ^

그리디 싫어