알고리즘 2343 자료

문제 요구사항

• 모든 레슨을 M 개 이하의 블루레이로 담아야함.
  • 블루레이의 크기를 최소화 해야한다
• 블루레이 가능한 범위는
  • 가장 긴 레슨 길이 ~ 모든 레슨 길이의 합
  • 일단 블루레이에는 무조건 하나 이상은 들어가야한다.

분석

1. 블루레이에 들어갈 수 있는 최소는 가장 긴 레슨 길이임

   • 모든 레슨이 일단 블루레이 안에는 들어갈 수 있어야 하기에, 블루레이의 크기가 가장 긴 레슨 길이가 최소가 되는거임
   • 일단 하나의 블루레이에 모든 레슨이 들어갈 수도 있기에 모든 길이의 합이 최대가 되는거고

2. 결정 문제

   크기가 X 인 블루레이로 M 개 이하의 모든 레슨을 담을 수 있는가?

   일단 이분탐색으로 M 개 이하의 레슨을 담을 수 있다면, 더 작은 크기로 중간값을 계산

   M 개 초과가 필요한 경우 더 큰 크기를 시도한다.