파이썬 백준 2512번: 예산

문제 

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

2512번: 예산

 

 

풀이

이진탐색으로 해결했다.

1. start를 1, max를 입력받은 가장 큰 예산으로 설정한다.

2. start가 end보다 커지기 전까지 반복한다 (이진탐색)
2-1. mid는 star와 end의 중간값 = 예산 값이다

2-2. 예산값이 요청받은 예산값도가 크면 요청받은 값을그대로, 작으면 예산값만큼만 result에 더한다

2-3  result값이 국가예산의 총액(M)보다 크면 예산을 더 줄여야하므로 end값을 현재 예산값(mid)보다 줄인다

2-4 result값이 국가예산의 총액(M)보다 작으면 최댓값을 찾기 위해 start값을 현재 예산값(mid)보다 늘린다

import sys
N =int(sys.stdin.readline())
money=list(map(int,sys.stdin.readline().split(' ')))
M=int(sys.stdin.readline())
start=1
end=max(money)
while(start<=end): #이진 탐색
    mid=(start+end)//2
    result=0
    for i in money:
        if mid>i:
            result+=i
        else:
            result+=mid
    if result>M: 
        end = mid - 1
    else :
        start = mid + 1
print(end)

 

 

😣덧)

처음에 if result>=M 으로 써서 틀렸다.

최댓값을 찾는 문제이기 때문에 result가 같은경우에는 start를 키워야한다!