[Python] S3_2512_예산 💰

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

문제

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.

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

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

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다.

여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.

입력

첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다.

출력

첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다.

예제

조건

• 시간 제한: 1초
• 메모리 제한: 128MB

코드

import sys
input = sys.stdin.readline

# 입력
N = int(input())
demand = sorted(list(map(int,input().split()))) # 각 지방의 예산 요청
budget = int(input())         # 총 예산
n_lst = range(1,demand[-1]+1) # 이분탐색을 위한 리스트

# Binary Search
start,end = 0,len(n_lst)-1
while start <= end:
    mid = (start+end)//2 # 중간 인덱스
    limit = n_lst[mid]   # 상한액 설정
    Sum = 0              # 상한액에 따른 합
    # 예산 요청 파악
    for num in demand: 
        if num < limit:
            Sum += num
        else:        
            Sum += limit
    # 중간 인덱스 재설정        
    if Sum < budget:
        start = (mid+1)
    elif Sum > budget:
        end = (mid-1)
    else:
        print(n_lst[mid])
        exit(0)

# 출력
if Sum > budget:  # 총 예산을 초과했을 경우        
    print(n_lst[mid-1])
else:
    print(n_lst[mid])

1. 각 지방의 예산 요청 demand 를 입력 받은 후, 정렬해준다.

2. 이분 탐색을 진행하기 위해, range(1,demand[-1]+1) 의 리스트를 만들어준다.

3. 중간 인덱스 mid 에 해당하는 상한액 limit 을 통해서 합 Sum 을 구해준다.

• 예를 들어 demand 가 [110,120,140,150] 이고, limit 이 130이라면, Sum 은 110 + 120 + 130 + 130 으로 490 이 된다.

• 현재 Sum 이 budget 인 485 보다 크므로, end 를 왼쪽으로 옮겨준다.

• 이러한 과정을 반복하며, 가장 budget 에 근사한 값을 찾는다.

4. Sum 이 budget 보다 큰 상태로 limit 값이 구해졌을 가능성이 있기 때문에, 다시 한 번 확인해준다.

• 만약 초과했을 경우에는, n_lst[mid] 이 아닌 n_lst[mid-1] 을 출력해준다.

느낀 점 & 배운 점

1. 처음에는 어떻게 문제를 풀어나가야할지 고민을 했는데, 근사치를 찾는다는 점에서 이분탐색을 활용하기로 한 점이 좋았던 것 같다.

2. 이제 와서 보니 굳이 인덱싱을 위해 mid 를 만들지 않고, range(0,demand[-1]) 로 설정했으면 더 보기 좋았을 것 같다.