이진 탐색 문제풀이(feat:백준 히오스)

입국 심사

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

문제
성권이는 Heroes of the Storm 프로게이머 지망생이다.

이 게임에는 총 N개의 캐릭터가 있다. 그리고 현재 각 캐릭터의 레벨은 Xi이다. 성권이는 앞으로 게임이 끝날 때까지, 레벨을 최대 총합 K만큼 올릴 수 있다.

팀 목표레벨 T =min(Xi) (1 ≤ i ≤ N)라고 정의하면, 게임이 끝날 때까지 성권이가 달성할 수 있는 최대 팀 목표레벨 T는 무엇인가?

예를 들어, N = 3, X1= 10, X2= 20, X3= 15이고 K = 10일 때, X1을 7만큼 올리고 X3을 2만큼 올리면 최소 레벨 Xi는 17이 된다. 따라서 팀 목표레벨 T는 17이다. 이 경우처럼 레벨을 총합 K보다 적게 올릴 수도 있다.

입력
첫째 줄에는 캐릭터의 개수 N, 올릴 수 있는 레벨 총합 K가 주어진다. (1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000)

다음 N개의 줄에는 현재 각 캐릭터의 레벨이 X1, X2, X3, ... , Xn 으로 주어진다. (1 ≤ Xi ≤ 1,000,000,000)

출력
가능한 최대 팀 목표레벨 T를 출력한다.

풀이방향 및 코드

풀이 방향

(1) 제일 큰 수를 찾아서 기준점 정하기

(2) 제일 작은 수도 기준점 정하기

(3) 각 능력치를 대입하면서 최댓값 찾아가기

function solution(N, K, array) {
  // 제일 큰 수를 찾아서 기준점 정하기
  // 제일 작은 수도 기준점 정하기
  // 각 능력치를 대입하면서 최댓값 찾아가기

  // 최소 레벨이 배열의 첫 값
  let left = array[0];
  // 최대는 가장 큰 값에 K만큼 더한 값
  let right = array[N - 1] + K;

  let answer = left;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    let j = 0;

    // mid 레벨로 만들기
    for (let i = 0; i < N; i++) {
      // 목표 레벨보다 작을 경우(// 클경우는 패스)
      if (array[i] < mid) {
        j += mid - array[i];
      }
    }
    if (j <= K) {
      // K이하라면, 최소 레벨을 높일 수 있음
      answer = mid;
      left = mid + 1;
    } else {
      //K초과했으면, 목표레벨 낮추기
      right = mid - 1;
    }
  }

  return answer;
}

정리

• 한 번 풀어보고 다시 접해보니 , 조금 더 수월하게 접근할 수 있었습니다.