[백준] 2512번: 예산 (sol.x)

풀이시간: 1시간

1. 나의 풀이

from bisect import bisect_left, bisect_right

N = int(input())
money = sorted(list(map(int, input().split(' '))))
total_money = int(input())

real_total = sum(money)

if real_total > total_money:
    i = -1
    while True:
        h_money = money[i]
        h_money_count = abs(bisect_left(money, h_money) - bisect_right(money, h_money))
        have_money = total_money - sum(money[:i - h_money_count + 1])
        renew_h_money = int(have_money / -(i - h_money_count + 1))

        if len(money) > -(i - h_money_count) and renew_h_money < money[i - h_money_count]:
            i -= h_money_count
            continue
        else:
            print(renew_h_money)
            break

else:
    h_money = max(money)
    print(h_money)

• 정렬을 하고 마지막 값을 상한선으로 설정
• 상한선과 같은 값 카운트
• 예산에서 상한선 미만의 요소들의 합을 뺌
• 남은 예산에서 상한선 이상의 요소들 만큼 나눔
• 상한선의 기준이 된 요소 앞의 값과 비교
• 상한선의 값이 더 낮다면 기준을 앞으로 옮기고 반복
• 47% 틀렸습니다. (반례들이 많은 듯...)

2. 또다른 풀이

N = int(input())
req = list(map(int, input().split()))
M = int(input())

lo = 0
hi = max(req)
mid = (lo + hi) // 2

def is_possible(mid):
    return sum(min(r, mid) for r in req) <= M
    
while lo <= hi:
	if is_possible(mid):
        lo = mid + 1
        ans = mid
    else:
    	hi = mid - 1
        
    mid = (lo + hi) // 2

print(ans)

• 상한선을 설정하고 총합 계산
• 상한선을 중간값으로 설정하고 비교를 반복
• 중간값의 기준이 되는 최솟값, 최대값이 같아지거나 역전이 될때 스탑

3. 보완할 것

• 기준을 설정해야 할 때 주어진 요소들만 가지고 하지 말고 자체적으로 계산하는 접근이 필요
• 함수 활용
• 상황을 일단 그려본다.