백준 2512: 예산 - 이분탐색(파이썬)

예산 성공

2512번: 예산

문제

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다. 

여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.

입력

첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다. 

출력

첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다. 

 

내 코드

 

import sys
n=int(sys.stdin.readline())
priceList=list(map(int, sys.stdin.readline().split()))
limit=int(sys.stdin.readline())

#정답은 1~가장 큰놈 사이에 있다
start, end=1,max(priceList)

#start가 end를 역전하면 탐색 종료임!
while start<=end:
    mid=(start+end)//2 #start~end 중간값 mid
    total=0 #합을 저장할 total

    for price in priceList:
        if price>mid: #mid보다 값이 크면,
            total+=mid #mid로 더하기.
        else: #mid보다 값이 작거나 같으면,
            total+=price #고유 값을 더하기.
    
  
    if total<limit: #목표치보다 작으면,
        start=mid+1 #더 큰 mid를 찾아야함. (mid+1~end 탐색)

    elif total>limit: #목표치보다 크면,
        end=mid-1 #더 작은 mid를 찾아야함. (start~mid-1 탐색)

    else: #total==limit이면 알맞은 mid를 찾았으므로 끝!
        end=mid #end를 mid값으로 세팅하고
        break #끝났으므로 while문을 빠져나가자.
    
print(end)

 

풀이 및 접근)

- 처음에는 노가다스러운 방식으로 풀었는데 이 문제는 이분 탐색을 활용한 문제였다.

- 최대로 배정될 수 있는 예산은 1~주어진 예산의 최대값 중에서 될 수 있다. 그러면 저절로 저 두 사이의 값이 답이라는 것인데, 여기서 이분 탐색을 떠올려야 한다.

- 특정 mid 값을 기준으로 문제의 조건을 통해 합을 구해 limit보다 작은지 큰지 판단하여 start와 end를 조절해야 한다.

- 특히 답을 end로 출력한 이유는, while문 탈출 조건이 start>end이면 빠져 나가는 것인데, start>end의 상황에서 mid는 end--mid--start의 순으로 위치해 있다. 이 때 답으로 start를 선택하게 되면, mid보다 큰 start로 합을 이루게 되어, limit보다 미세하게나마 커지게 되어서 문제의 조건들을 충족하지 못한다. end를 답으로 선택해야 limit에 미세하게나마 작으면서 제일 가까운 값을 얻어낸다.

- 물론 while문 안의 과정 안에서 total==limit을 만족하는 순간이 올 수도 있다. 이 때는 고민할 필요없이 그 때의 mid가 답이 되는 것이다. 위의 설명에서 end로 답을 출력하기로 했으므로 end=mid를 통해 답을 end에 할당하는 것을 이해할 수 있을 것이다.