JArchive 프로그래밍 일기

기타레슨 문제 링크

리뷰 

강의 전부가 M장 블루레이에 담겨야 한다. 따라서 블루레이 크기가 최소 몇분이 되야 하는지 찾는 문제다. 

이분탐색의 타겟은 블루레이의 크기다. 

블루레이의 크기는 최소 1분, 최대 모든 강의의 크기 중에서 탐색할 수 있다.

주의할 점은 블루레이의 크기보다 강의 하나의 크기가 큰 경우도 있을 수 있다는 점이다. 

main 함수 while문에서 이분탐색을 한다.

if문의 b_search() 함수는 블루레이가 mid크기의 강의를 담을 수 있다고 했을 때, M장의 블루레이만으로 모든 강의를 담을 수 있는지 확인하는 bool 함수다. 

이분탐색 문제는 무엇을 주제로 이분탐색 할 지를 잘 생각하고 시작해야되니까 연습이 좀 필요한 것 같다. 

"맞았습니다" 코드 

#include <bits/stdc++.h>
using namespace std;

int N, M, answer, front, mid, back;
int blue[100001]; // 강의 길이 목록

bool b_search(int mid){ // mid 크기의 M장 블루레이에 모두 담기는지 확인.

  int sum_time = 0, cnt = 1; // sum_time 은 mid 이하여야 한다. 블루레이 개수 cnt.

  for(int i = N-1; i>=0; i--){

    if(blue[i] > mid){
      return false; // 블루레이 1장에 강의 1개도 못들어가는 경우.
    }

    sum_time += blue[i];
    if(sum_time > mid){
      cnt++;
      sum_time = blue[i];
    }
  }
  return M >= cnt; // 블루레이 개수가 M이하라면 만족.
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> N >> M;
  for(int i = 0; i < N; i++) {
    cin >> blue[i];
    back += blue[i]; // 모든 강의 길이를 더해서 back에 저장 
  }
  front = 1; // 1분

  while(front <= back){

    mid = (front + back) / 2; // 블루레이 1장의 크기 mid

    if(b_search(mid)){ // mid크기의 블루레이로 M장 이하에 담을 수 있는지?
      answer = mid;
      back = mid-1;
    }else{
      front = mid+1;
    }
  }
  cout << answer;
  return 0;
}