[백준] 2512번 예산(파라메트릭 서치)(Python - 파이썬)

백준 2512번 문제입니다. (solved.ac)기준 실버 3 문제입니다.

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

2512번: 예산

n개 지방에서 각각 요청 예산을 입력 받고 예산의 총액(M)에서 2가지의 조건을 만족시키도록 예산 배정을 하면 되는 문제입니다.

1번 조건 : 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.

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

 주어진 범위 내에서 원하는 조건을 찾는 문제이므로 파라메트릭 서치(parametric Search)를 이용하여 문제를 해결하였습니다.

정답 코드

import sys

# 지방의 수(n)을 입력 받음
n = int(sys.stdin.readline().rstrip())

# 지방의 예산요청(req)을 공백기준으로 입력 받음
req = list(map(int, sys.stdin.readline().rstrip().split()))

# 총 예산(m)을 입력 받음
m = int(sys.stdin.readline().rstrip())

# 이진탐색을 위하여 오름차순 정렬
req.sort()

# 예산의 최솟값(시작점)
start = 1
# 예산의 최댓값(끝점)
end = max(req)
# 정답을 담을 변수
result = 0

# parametric search
# 파라메트릭 서치를 활용하여
# 시작점이 끝점보다 커지면 탐색 종료
while (start <= end):

    # 배정한 예산
    total = 0

    # 줄 수 있는 최대 예산
    mid = (start + end) // 2

    # 하나씩 비교해보기
    # 각 지방의 요청 예산(req)이 줄 수 있는 최대 예산(mid) 보다 크면
    # 줄 수 있는 최대 예산(mid)이상은 줄 수 없기 때문에
    # 배정한 예산(total)에 줄 수 있는 최대 예산(mid)만큼 증가
    for x in req:
        if x > mid:
            total += mid
        # 지방 별 요청 예산(x)이 최대 예산(mid) 보다 작으면 요청한 만큼만 주면 되므로
        # 요청 예산만큼 배정한 예산(total)을 증가
        else:
            total += x


    # 배정한 예산(total)이 총 예산(m)보다 같거나 적다면
    # 줄 수 있는 최대 예산(mid)를 늘려줘야 하므로
    # start = mid + 1를 해주어 다음 줄 수 있는 최대 예산(mid)이 증가하게 만들어줌.
    # result(정답값)에 현재 줄 수 있는 최대 예산(mid)를 넣어줌.
    if total <= m:
        start = mid + 1
        result = mid
    # 배정한 예산(total)이 총 예산(m)보다 크다면 줄 수 있느 최대 예산(mid)를 줄여야 하므로
    # end = mid - 1을 해주어 다음 줄 수 있는 최대 예산(mid)을 줄여줌.
    else:
        end = mid - 1

print(result)

비슷한 유형의 문제들

[백준] 2805번 나무 자르기(파라메트릭 서치(Python)

[백준] 2805번 나무 자르기(파라메트릭 서치(Python)

[백준] 2110번 공유기(파라메트릭 서치)(Python)

[백준] 2110번 공유기(파라메트릭 써치)(Python)

[백준] 1654번 랜선 자르기(파라메트릭 서치)(Python)

[백준] 1654번 랜선 자르기(파라메트릭 서치)(Python)