[알고리즘] 이분 탐색(binary search) / 1654 : 랜선 자르기

💡 이분 탐색이란?

결정 문제(decision problem)의 답이 이분적일 때, 사용할 수 있는 탐색 기법

이분 탐색은 최적화 문제와 결정 문제로 구성된다.

1) 최적화 문제 : 조건을 만족하는 최대/최소 찾기
★최적화 문제에 단조성이 있다면 이진 탐색 알고리즘 적용가능
2) 결정 문제 : 임의의 X가 조건을 만족하는지 확인

단조성이 있다는 것은 문제를 풀어보며 직접 이해하는 것이 빠를 것이다.
이진 탐색 알고리즘의 시간복잡도는 O(TlogX)로,
T: 결정문제 한번 푸는 데 걸리는 시간, X: 답의 후보 길이 이다.

이분 탐색 알고리즘을 이용한, 조건을 만족하는 최댓값을 도출해내는 템플릿은 다음과 같다.

조건을 만족하는 최댓값 구하기

bool chk(int X) {
	// X가 해당 조건을 만족하는가?
}
int lo=, hi=, ans= // lo, hi변수 초기값 주의(범위 설정)
while(lo<=hi) {
	int mid = (lo+hi)/2;
    if(chk(mid)) { // mid가 조건을 만족한다면
    	lo = mid+1; // 답의 후보를 (mid, hi]로 조정
        ans = mid; // mid를 ans에 저장하며 업데이트
    }
    else // mid가 조건을 만족하지 않는다면
    	hi = mid-1;
}
// ans에 조건을 만족하는 최댓값이 저장되어있다.

문제 풀러 바로가기 >> 1654 랜선 자르기

✔️ 문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

🚩 입력

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 2^31-1보다 작거나 같은 자연수이다.

🚩 출력

첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

🤔 내가 생각한 아이디어

우선, 그냥 1부터 랜선 최대길이까지 다 탐색할 수는 없나? 라고 생각했는데,
랜선의 길이 범위가 2^31-1이므로 시간 초과가 뜰 것 같았다.
따라서 저번 무지성 선형 탐색으로 풀면 안되겠다는 생각을 했다.
그렇다면 생각할 수 있는 것은 이분 탐색. 해당 문제를 이분 탐색으로 풀 수 있을지 알기 위해서, 해당 문제가 단조성을 만족하는지 예시로 입력된 값의 예시를 통해 확인해보자.

각 랜선의 갯수(N)은 총 4개로, 필요한 랜선은 11개(M)이다.
첫 입력인 길이가 802인 랜선에서, 만들 수 있는 최대길이는 어떻게 확인할 수 있을까? 우리가 랜선의 길이를 200으로 설정하면 랜선 4개를 가져갈 거고, 랜선의 길이를 40으로 설정하면 랜선 20개를 가져갈 것이다.

☝️STEP 1. 최적화 문제 설정

for(i =0 to k) sum+=(len[i]/mid) //sum에는 가져가는 랜선 갯수
if sum>=N이면 조건 만족

• 랜선 당 길이(mid)의 값을 늘리면, 가져가는 랜선의 갯수는 줄어든다.
• 랜선 당 길이(mid)의 값을 줄이면, 가져가는 랜선의 갯수는 늘어난다.
• mid로 설정했을 떄, 랜선의 갯수가 가져가야 할 랜선의 입력값 갯수 M보다 크면 해당 mid값은 채택된다.

✌️STEP 2. 결정 문제

• 이 mid값 중에서 최댓값을 구하는 문제다.

우리의 문제 조건은 mid를 설정하고, mid를 설정했을 때 가져가는 랜선의 갯수가 N보다 크면 탐색범위를 (mid, hi]로 줄인다.

💻 정답 코드

#include <iostream>
#include <algorithm>
using namespace std;
int k, n; //랜선 입력수, 가져가려는 랜선 수
int len[1000004]; //설정하려는 랜선 길이를 오름차순으로 담은 배열
bool chk(int mid){ //mid가 조건을 만족하는가?
  long long int sum = 0;
  for(int i = 0; i < k; i++){
    sum += len[i]/mid;
  }
  if(sum>=n) return true;
  else return false;
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cin >> k >> n;
  int mx_len = -987654321;
  for(int i = 0; i < k; i++) {
    cin >> len[i];
    if(len[i]>mx_len) mx_len=len[i];
    //mx_len = max(len[i], mx_len);
  } 
  //탐색 범위를 설정한다. (1,mx_len], 
// 입력에서는 (1, 802]
  long long int lo = 1;
  long long int hi = mx_len, ans = 0;
  //조건을 만족하는 랜선의 길이 중 최댓값을 구하는 알고리즘
  while(lo<=hi){
    long long int mid = (lo+hi)/2;
    if(chk(mid)) {
      lo = mid+1;
      ans = mid;
    }
    else
      hi = mid-1;
  }
  cout << ans << "\n";
}