boj_2512_예산

2512번: 예산

알고리즘 생각

1. 예산을 낭비하지 않고 최대로 사용할 수 있는 `상한선`을 구하는 것이 목표
2. 평균값을 내림으로 계산하면 일단 예산을 넘지 않는 `상한선`을 만들 수 있다
3. 이 `상한선`은 최대치가 아니라 예산이 분명 낭비된다. 여기서부터 최소 단위씩 올려가면서 비교해야한다.

 

구현방법 및 코드

• 빈 배열을 만들고, 조건에 맞게 초기화해가면서 계속 비교해나간다.
• 이 과정에서 len() 과 sum() 함수를 사용하니 매우 편했다

import math

n = int(input())
budgets = list(map(int,input().split( )))
total_budget = int(input())

if sum(budgets) <= total_budget:
    print(max(budgets))
else:
    temp_budgets = []
    avg_budget = math.floor(total_budget / n)
    for budget in budgets:
        if avg_budget >= budget:
            temp_budgets.append(budget)
    max_budget = (math.floor((total_budget-sum(temp_budgets))/(n-len(temp_budgets))))

    while max_budget *(n-len(temp_budgets)) +sum(temp_budgets) <= total_budget:
        max_budget += 1
        temp_budgets = []
        for budget in budgets:
            if max_budget >= budget:
                temp_budgets.append(budget)

    print(max_budget-1)

 

후기

• 이분 탐색을 이용하는 알고리즘 문제라 하는데, 그리디로 풀어버린 거 같다... 솔직히 어떻게 이분 탐색을 생각하는 지가 더 신기하다..
• leetcode였으면 메모리 초과나 시간 초과 나서 터졌을 거 같다.. 코드를 list가 아니라 cnt로 바꾸면 더 좋을 거 같은데 다음에는 그렇게 해야겠다