혼자 공부하는 공간

안녕하세요 GODZ입니다. 오늘은 이분 탐색을 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 정렬한 뒤, 최대값에서 빼가면서 총 예산(M)을 맞추는 것은 각 예산 값들이 100,000 이하인 것을 감안하면 시간 제한(1초)를 맞출 수 없다. 따라서 이분 탐색을 통해 시간 복잡도를 log로 변환하여 작업을 줄이도록 한다. 예산의 값 중 최대값을 찾는다. 최소값과 최대값의 평균값(mid)을 구해 각 예산에 상한선을 적용한 뒤, 총 예산과 비교한다. 총 예산보다 작으면, mid값을 저장하고 mid값을 최소값으로 설정한 뒤 4번 작업 반복. 총 예산보다 크면, mid값을 최대값으로 설정한 뒤 4번 작업 반복. 최대값과 최소값이 같으면 반복을 종료하고, 저장된 mid값 중 가장 큰 값을..