[Python] 백준 2512 예산 - 구현 & 이진 탐색

백준 홈페이지 문제와 개인적인 해설을 작성한 글 입니다.

 

백준 문제 - 2152번 : 예산

2512번: 예산

 

---

 

입력

 

첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 

다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 

이 값들은 모두 1 이상 100,000 이하이다. 

그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다.   

 

출력

 

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

 

예제 입력 1	예제 출력 1
4 120 110 140 150 48	127

 

예제 입력 2	예제 출력 2
5 70 80 30 40 100 450	100

 

코드를 보기 전에

 

필자는 이 문제를 이진 탐색으로 풀기 전에 직접 구현으로 풀면 되지 않을까 싶어 문제를 풀었다. 그래서 시원하게 실패하고 접고, 이진 탐색으로 풀었다. 사실 반례를 못 찾기도 했고, 20분 ~ 30분을 잡고 푸는게 맞다고 생각했지만, 여러 오류가 나서 틀렸습니다. 이진 탐색으로 푸시고, 반례를 아신다면 댓글을! 수정할 점을 알려주시면 감사하겠습니다. 가장 기본적인 이진 탐색 문제입니다.

 

코드 - 구현 (틀림)

 

# 4
n = int(input())

# 120 110 140 150
array = list(map(int, input().split()))

# 485
sum = int(input())
avg = sum // n # 평균 값

dif = 0 # 차이 값
maxDe = max(array) # 예금 중 최댓값

sumDe = 0

count = 0

for i in array:
  sumDe += i

if (maxDe <= avg):
  print(maxDe)

if (maxDe > avg):
  
  if(sumDe <= sum):
    print(maxDe)
  
  else:
  	
    for i in array:
      if avg >= i :
        sum -= i
        count += 1
    
    print(sum // (n - count))

 

코드 - 이진 탐색 (통과)

 

# n 개 입력받기 
n = int(input())

# 예산 각각 입력받기
array = list(map(int, input().split()))

# 총 예산 입력 받기
sum = int(input())

# 이진 탐색 기본
start, end = 0, max(array)

while start <= end:
  mid = (start + end) // 2
  result = 0
  # 최대로 입력 받기
  for i in array:
    if mid >= i:
      result += i
    else:
      result += mid
  # 이진 탐색 기본
  if result >= sum:
    end -= 1
  else :
    start += 1

print(end)