[틀림] 백준 2343 기타레슨 // 매개변수 탐색, 음수기반 카운팅

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

* 풀이

• 완탐 : 이중 for문
• 이분탐색 : 첫번째 for문을 이분탐색으로 교체

 

• go 함수 구현이 빡센문제
• f(1)이 거짓이 나와야 되는 문제 발생
  • 예외처리 필요
  • 어떤 강의가 블루레이보다 긴경우, 무조건 false를 반환하도록 처리 필요.
  • 강의 중 하나라도 Blu-ray 용량보다 긴 경우, 해당 용량(x)은 적합하지 않으므로 무조건 false를 반환.

• en= mid-1
• st = mid +1

• 음수기반 카운팅 필요
  • 양수기반은 case가 많아져서 너무 복잡

// x : 빼고 남은크기
int temp = x; // 블루레이의 크기 저장
int cnt = 0;
for(int i = 0; i < n; i++){
   if(x - a[i] < 0){ // 블루레이가 꽉 찰때마다 카운팅
      x = temp; // 남은크기 초기화
      cnt++; // 1칸사용
   }
   x -= a[i];
}

 

• 초기화 주의
  • 최대 길이 = 10000분 * 최대갯수 여야함

int st=1;
int en=100000*10000; // 주의!

 

• while(st<en) VS while(st<=en)

 

* 전체코드

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

int n, m;
int a[100000+4];

bool go(int x) { // 블루레이의 크기가 x일때, 가능한지 확인
   // 예외처리: 어떤 강의든 블루레이 크기보다 클 수 없음
   for(int i = 0; i < n; i++){
      if(a[i] > x){
         return false;
      }
   }

   // 블루레이 크기가 x일 때 필요한 블루레이 개수 계산
   int temp = x; // 현재 블루레이의 남은 공간
   int cnt = 1;  // 블루레이 개수 (처음부터 1개로 시작)
   
   for(int i = 0; i < n; i++){
      if(temp - a[i] < 0){ // 현재 블루레이에 더 담을 수 없을 때
         temp = x;         // 새 블루레이 사용
         cnt++;            // 블루레이 개수 증가
      }
      temp -= a[i];        // 현재 블루레이에 강의 추가
   }
   
   return cnt <= m;  // m개 이하의 블루레이로 가능한지 반환
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);

   cin >> n >> m;
   
   int sum = 0;
   int max_lecture = 0;
   
   for(int i = 0; i < n; i++) {
      cin >> a[i];
      sum += a[i];
      max_lecture = max(max_lecture, a[i]);
   }

   int st = 1; 
   int en = sum;          // 최대 크기는 모든 강의 길이의 합
   int ret = 0;
   
   while(st <= en) {
      int mid = (st + en) / 2;
      
      if(go(mid)) {
         ret = mid;       // 가능한 경우 결과 저장
         en = mid - 1;    // 더 작은 크기 시도
      } else {
         st = mid + 1;    // 더 큰 크기 필요
      }
   }
   
   cout << ret;           // 가능한 최소 크기 출력
}