Boj 2512번 예산 python

이분 검색(결정 알고리즘) 이용

첫번째 시도(틀림)

n=int(input())
budget_list=list(map(int, input().split()))
budget_sum=int(input())

min_budget=budget_sum//n
max_budget=max(budget_list)
res=0

while min_budget<=max_budget:
    mid=(min_budget+max_budget)//2
    for i in range(n):
        if budget_list[i]>mid:
            budget_list[i]=mid
            #여기에서 오류 만약 이전의 mid값이 현재의 mid값보다 작다면 리스트 상에서 변화는 없다
            

    if sum(budget_list)<=budget_sum:
        res=mid
        min_budget=mid+1
    
    else:
        max_budget=mid-1


print(min_budget)
print(res)
print(mid)
print(max_budget)
print(budget_list)

기존 값을 고정값으로 두고 다른 수단을 이용하는 방법 vs 기존 값을 단계별로 수정하는 방법

위의 경우는 리스트 값을 고정하고 다른 변수를 설정해서 코드를 작성함

더 나은 방법임!

 

두번째 시도(답)

n=int(input())
budget_list=list(map(int, input().split()))
budget_sum=int(input())

min_budget=0
max_budget=max(budget_list)

res=0

while min_budget<=max_budget:
    num=0 
    #num=0가 루프 안에 있어야 함!!
    mid=(min_budget+max_budget)//2
    for i in range(n):
        if budget_list[i]>mid:
            num+=mid
        else:
            num+=budget_list[i]
            

    if num<=budget_sum:
        res=mid
        min_budget=mid+1
    
    else:
        max_budget=mid-1


print(res)

*num=0를 루프 밖에 작성하여 오류가 났음

루프 안에 작성하여 지속적으로 값이 초기화 되어야 함!