[Programmers] 예산

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

문제의 핵심은

"항상 정확히 신청한 금액만큼 지원해 줘야 하므로 남은 2원으로 나머지 부서를 지원해 주지 않습니다."

이 부분인데, 남은 금액이 있어도 된다는 뜻이다.

그러니까 budget을 꽉 채우려고 하지 말고 남아도 괜찮으니 가장 많이 지원해줄 수 있는 방법을 찾으라는 문제다.

def solution(d, budget):
    d.sort()
    answer = 0
    sum = 0
    for i in d:
        if sum + i <= budget:
            sum += i
            answer += 1
        else:
            break
    return answer

우선 배열을 정렬하고, 그 배열의 첫번째 요소보다 budget이 적으면 아예 지원이 불가능 한 상태이다.

그렇지 않으면 요소들을 더해서 sum에 넣어주고, 이 sum이 budget보다 커지기 전까지 for문을 이용한다.

answer를 이용하여 지원가능한 부서 수를 카운트해준다.

진짜 간단했는데 괜히 어렵게 생각해서 2시간을 헤맸따....

~내가 삽질했던 코드~

# from itertools import combinations

# def solution(d, budget):
#     if sum(d) <= budget:
#         return len(d)
#     else:
#         for j in range(len(d),1,-1):
#             l = list(combinations(d, j))
#             for i in range(len(l)):
#                 if sum(l[i]) <= budget:
#                     return len(l[i])
#         if budget in d:
#             return 1
#         else:    
#             return 0

1. combination을 이용하여 모든 경우의 수를 다 뽑는다.

combination을 이용하면
[(1),(2),(3)...]
[(1,2),(1,3),....]

이런식으로 1부터 배열의 길이까지 모든 경우의 수를 뽑아 주는데 이 문제에서는 거꾸로 뽑았다.

이유는 최대한 많이 지원을 해줘야 해서 그렇다.

2. budget과 list 안의 combinations을 검사한다.

list안에는 모든 경우의 수가 tuple로 들어가 있다.

이 튜플을 sum함수를 이용하여 더해준 다음, 적거나 같은 경우에만 return값 튜플의 길이, 즉 지원 가능한 부서를 숫자로 돌려준다.

크다면 다시 올라가서 다음 가짓수를 계산한다.

3. 메모리를 조금이라도 절약하고자 한 나의 노력...^_ㅠ

combination을 2개의 조합까지만 만들었다. [(1), (2), (3)...] 즉 각 요소들은 만들지 않았다는 말...

왜냐하면 for문 실행을 한번이라도 더 줄이려고.....

그래서 리스트 d 안에 budget이 있으면 1을 리턴하고, 아닐경우에는 아무도 지원해줄 수 없다는 말이므로 0을 리턴한다.

후기

정답은 나오는데 절반이상이 시간초과라서 이게 머선129 싶었다...
결국 구글링을 통해 도움을 받았다ㅠ
어쩐지 레벨1인데 왜이렇게 어렵나 싶었는데...
간단하게 생각하면 될걸 너무 꼬와서 생각해버렸다....
내가 직접 생각하지 못해서 아쉽지만 combination을 다시 공부할 수 있었음