[백준 2512번] 예산 (Python 파이썬) 풀이 방법

백준 2512번 <예산> 문제 보기

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

2512번: 예산

 

 

백준 2512번 <예산> 문제 풀이

n = int(input().rstrip())
requests = list(map(int, input().split()))
m = int(input().rstrip())

if sum(requests) <= m:
  print(max(requests))
else:
  start, end = 1, max(requests)
  answer = 0
  while start <= end:
    mid = (start + end) // 2

    count = 0
    for budget in requests:
      if mid >= budget:
        count += budget
      else:
        count += mid
        
    if count > m:
      end = mid - 1
    elif count == m:
      answer = mid
      break
    else:
      start = mid + 1
      answer = mid
      
  print(answer)

 

 

- 접근 방식

 

문제 유형 자체가 지난 번에 풀었던 [2805번 나무 자르기]와 유사하다는 느낌을 받았다. 균등하게 분배할 수 있는 상한선을 찾는 문제 유형이었다. M의 범위가 굉장히 크다는 점에서 이분탐색을 써야하는건가? 싶었는데 정확한 이유나 로직이 좀 헷갈려서 회의 때 토론해보면 좋을 것 같다고 생각했다!

 

 

- 코드 설명

 

우선, if 문을 통해 예산안 총합이 m보다 작다면 문제에서 주어진 대로 요청한 금액 중 최댓값을 반환하도록 하였다. 그렇지 않을 경우, else 문에서 그 상한값을 찾아야 한다.

M이 N 이상 1000000000 이하라고 하였기에 start와 end값을 그렇게 잡아도 됐겠지만, 정석대로 1과 max(예산안) 값으로 설정해주었다.

이분탐색을 한 회씩 거칠 때마다 mid값이 budget보다 크거나 같다면, 요청한 예산안만큼만 배정해주어도 되므로 count에 budget을 더해주었고, mid값이 budget보다 작다면 상한값보다 요청한 예산이 더 크므로 count에 mid를 더해주도록 하였다.

이후, count가 m보다 크다는 것은 정해진 값보다 더 크게 상한값을 잡은 것이므로 end 위치를 조절해주었고, count가 m과 같다는 것은 말그대로 상한값이므로 바로 mid가 답이 되는 것을 알 수 있었다. 또, count가 m보다 작다는 것은 정해진 값보다 더 작게 상한값을 잡았다는 뜻이므로 start 위치를 조절해주었다.