[알고리즘] 이분탐색 - 백준 16564번

da__ell·2022년 10월 5일
0

DataStructure / ALGORITHM

목록 보기
5/23

해당 문제는 팀 내의 최소 레벨인 T의 최댓값을 출력하는 문제이다.

문제의 풀이 요점은 다음과 같다.

  1. 플레이어 레벨을 오름차순으로 정렬한다.
  2. 가능한 최솟값은 플레이어 레벨의 최솟값이 될 것이고, 최댓값은 플레이어 레벨 중 최댓값에 k를 몰빵한 값이 될 것이다.

최솟값이 최댓값을 넘지 않는 선에서 이분탐색을 진행한다.
tmp는 특정 레벨이 되기위한 레벨업에 필요한 경험치 값이다. (여기서는 midV가 되겠다.)

이분탐색을 진행하면서 각 플레이어 레벨이 중간값 미만일 경우 해당 중간값이 되기 위해 필요한 레벨을 tmp에 더해준다.
K가 tmp보다 레벨량이 높을 경우 최솟값을 올려주고 tmp보다 레벨량이 낮을 경우 최댓값을 줄여준다.
해당 탐색을 반복하여 최댓값을 출력하면 된다.

profile
daelkdev@gmail.com

0개의 댓글