[Python] 백준 2512. 예산

https://www.acmicpc.net/problem/2512

2512번: 예산

 

문제 설명:

국가예산이 주어졌을때

지방예산요청의 합이 국가예산보다 큰 경우 상한액을 설정

그 합이 가능한 국가예산을 벗어나지 않고 최대가 되도록 구하는 문제

 

만약 국가예산이 485이고 

지방예산요청이 120 110 140 150 일 때 합이 485를 넘어가게 된다.

그럼 상한액을 설정해서 상한액이 127이 될때 120 110 127 127이 되어 합이 484로 예산의 최대액이 된다.

 

• start, end의 값을 각각 0, max(지방예산요청) 으로 설정한다.
• 예산요청의 합을 구하는 curr 설정
• 반복문을 돌려줌
  • 요청한 금액이 상한액 이상이면 상한액을 더하고
  • 상한액 미만이면 요청한 금액 더하기

    mid = (start + end) // 2
    curr = 0
    for i in arr:
        if i >= mid:
            curr += mid
        else:
            curr += i

• 예산 총액이 국가 예산 이하라면 start 를 조정하여 상한액을 높이도록 한다.
• 예산 총액이 국가 예산을 초과한다면 end를 조정하여 상한액을 낮춰준다.

    if curr <= m:  # 예산 총액이 국가 예산 이하라면
        start = mid + 1
    else:  # 예산 총액이 국가 예산을 초과한다면
        end = mid - 1