백준 2512번 : 예산

<문제>

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

2512번: 예산

---

<코드>

import sys
input = sys.stdin.readline

N = int(input())
bud = list(map(int, input().split()))
M = int(input())
s, e = 0, max(bud)

while e-s >= 0:
    mid = (s+e)//2
    res = 0
    for i in range(N):
        if bud[i] >= mid:
            res += mid
        else:
            res += bud[i]
    if res > M:
        e = mid-1
    else:
        s = mid+1
print(e)

import sys
input = sys.stdin.readline

N = int(input())
bud = list(map(int, input().split()))
M = int(input())
s, e = 0, max(bud)

while e-s >= 0:
    mid = (s+e)//2
    res = 0
    for i in bud:
        res += min(mid, i)
    if res > M:
        e = mid-1
    else:
        s = mid+1
print(e)

---

<풀이>

• 예산을 입력받아 이분탐색을 위해 최소값 0과 최대값을 변수로 만든다.
• 최소값과 최대값이 동일할때까지 반복하여 mid값에 따른 배정될 예산을 계산한다.
• 배정된 예산보다 총 예산인 큰 경우 mid값을 작게햐야하므로 최대값 = mid-1, 그 반대인 경우 최소값 = mid +1로 설정한다.

 

• 배정한 예산보다 총 예산이 큰 경우 최대값을 mid -1, 반대인 경우 최소값을 mid+1로 설정해야 한다.
• Index로 생각할 때, 이분탐색의 경우 mid +/- 1을 해 주어야 하는 경우와 동일하게 수치인 경우도 계산을 위해 필요한 작업임

 

---

참고 : https://github.com/Junuux/Algorithm/tree/main/Silver/2512

GitHub - Junuux/Algorithm