[python] 백준 - 2512. 예산

🤔문제 해결

• S3 | 이분탐색

이분 탐색의 기본문제

이분탐색이란? 탐색 부분을 두 부분으로 분할해서 답을 찾는 과정이다.

 

1부터 10까지 값이 있다고 가정했을 때 7이란 값을 찾아보자

최소는 1이고 최대는 10이다. 절반으로 나누면 5인데

운이 좋아서 5가 맞으면 정답, 하지만 찾는 값은 7이므로 정답이 아니다

 

크기를 비교해서 찾는 값이 5보다 작으면 최대를 줄이고,

찾는 값이 5보다 크면 최소를 늘린다.

 

찾는 값이 5보다 크므로 최소를 늘린다.

최소는 절반+1 최대는 그대로 10이다. 절반으로 나누면 8

 

찾는 값은 8보다 작으므로 최대를 줄인다.

최소는 6 최대는 절반-1이다. 절반으로 나누면 6

 

찾는 값이 6보다 크므로 최소를 늘린다.

최소는 절반+1 최대는 7이다. 절반으로 나누면 7이므로 정답!

 

4번만에 정답을 찾았다. for문으로 돌면 7번만에 찾을것이다.

만약 값이 어마무시하게 커진다면 효율면에서 매우 큰 차이가 날 것이다.

우투리님 블로그 - https://wootool.tistory.com/62

 

 

💻소스 코드

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

left = 0
right = max(budgets)
result = 0
while right >= left:
    mid = (left + right) // 2
    answer = 0
    for budget in budgets:
        if budget > mid:
            answer += mid
        else:
            answer += budget

    # answer: 내가 책정한 총 예산, M: 최대 예산
    if answer > M:
        right = mid - 1
    else:
        left = mid + 1
        result = max(result, answer)
print(right)

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

2512번: 예산