백준 2512 예산 Python3

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

2512번: 예산

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ2512.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys

def getLimit(left, right, areas, N, M):
    answer = min(left, right)
    while left <= right:
        mid = (left+right)//2
        total = 0
        for area in areas:
            total += min(area, mid)
        if total > M:
            right = mid-1
        else:
            answer = mid
            left = mid + 1
    return answer

input = sys.stdin.readline
N = int(input())
areas = list(map(int, input().split()))
M = int(input())
left = min(min(areas), M//N)
right = max(areas)
print(getLimit(left, right, areas, N, M))

---

풀이 과정

풀이 시간 47분

문제의 핵심은 국가의 총 예산 M원을 사용하여 N개의 지방의 예산요청을 가능한 최대로 배정해야 한다.

이때, 특정 정수 상한액을 잡아 모든 지방의 예산 요청에 배정해야 한다.

즉, 정수 상한액을 구하기 위한 이분탐색을 진행하면 된다.

import sys

def getLimit(left, right, areas, N, M):
	#left와 right 중 작은 값을 answer로 초기화 한다. -> right가 더 작은 경우가 있을 수 있으므로
    answer = min(left, right)
    
    #이분 탐색
    while left <= right:
    	#정수 상한액을 mid로 가정
        mid = (left+right)//2
        #정수 상한액을 mid로 하여 예산요청을 모두 배정할 경우 필요한 총 예산
        total = 0
        for area in areas:
            total += min(area, mid)
        
        #total이 국가 총 예산보다 큰 경우, 
        if total > M:
        	#해당 mid 값으로 정수 상한액을 설정할 수 없으므로 right 범위를 줄인다
            right = mid-1
            
        #total이 국가 총 예산보다 작거나 같은 경우,
        else:
        	#해당 mid 값으로 정수 상한액을 설정할 수 있다
            answer = mid
            #이후 가능한 최대의 예산을 사용하는 정수 상한액을 찾기 위해 left 범위를 늘린다
            left = mid + 1
    return answer

input = sys.stdin.readline
N = int(input())
areas = list(map(int, input().split()))
M = int(input())

#정수 상한액의 최소 범위는 지방의 예산 요청의 최솟값과 국가 예산을 지방의 수로 나눈 값 중 더 작은 값으로 설정한다.
left = min(min(areas), M//N)
#정수 상한액의 최대 범위는 지방의 예산 요청의 최댓값으로 설정한다.
right = max(areas)
print(getLimit(left, right, areas, N, M))

#시간복잡도 = O(log n), 공간복잡도 = O(n)