2512. 예산

2512 문제 보기

접근 방식

처음에는 그리디로 접근하려 했으나, 현재 상황에서의 최적해만을 선택했을 때 전체 상황에서도 최적해가 되기에 어려울 것 같다고 생각했다.
그래서 start, end를 정해 mid값과의 대소관계에 따라 값을 조정해나가는 이분탐색으로 풀이하고자 했다.

기존 이분탐색 코드는 배열이 주어졌을 때 인덱스로 접근했었지만,
이분탐색은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 자료를 탐색하는 방법이기 때문에
start와 end 값을 0과 arr의 max 값으로 잡아줬다.

start, end = 0, max(arr) # 최솟값과 최대값 설정
mid = (start + end) // 2
ans = 0

다음 start <= end 조건에서 반복되는 while문 내부에서, 정답(ans)을 갱신하기 위한 조건으로 is_possible() 함수를 만들어 사용했다.

def is_possible(mid):
  return sum(min(cost, mid) for cost in arr) <= total

arr 내부의 원소들을 순회하며 mid과 arr의 원소 값 중 더 작은 값들을 찾아 총합을 구한다. 이 때 값들의 총합이 total보다 작은 경우에만 True를 리턴한다.

마지막으로 이분탐색의 기본 로직인 start, end, mid 값을 갱신해준다.
다만 ans를 갱신하는 조건으로 is_possible(mid)의 리턴값을 받아오기!

while start <= end:
  if is_possible(mid):
    start = mid + 1
    ans = mid
  else:
    end = mid - 1
  mid = (start + end) // 2

최종 코드

import sys
input = sys.stdin.readline

N = int(input().rstrip())
arr = list(map(int, input().rstrip().split()))
total = int(input().rstrip())

start, end = 0, max(arr) # 최솟값과 최대값 설정
mid = (start + end) // 2
ans = 0

def is_possible(mid):
  return sum(min(cost, mid) for cost in arr) <= total

while start <= end:
  if is_possible(mid):
    start = mid + 1
    ans = mid
  else:
    end = mid - 1
  mid = (start + end) // 2

print(ans)

배운점

▶️ 이분탐색 기본 로직 까먹지 말기
▶️ 이분탐색 내부에 값 갱신 조건 잘 파악하기