인프런 커뮤니티 질문&답변

43번 뮤직비디오(이분검색 응용 : 결정 알고리즘) 관련 두가지 질문이 있습니다.

1. 직접 코드를 다음과 같이 작성해보았는데 결과값이 잘 나오지 않아 어디서 오류가 생긴 것인지 궁금하여 질문드립니다.

#include<stdio.h>

#include<vector>

#include<algorithm>

using namespace std;

int main(){

   freopen("input.txt", "rt", stdin);

   int n, m, ans, i, cnt=1, lt=1, rt=0, mid, max=-2147000000, sum;

   scanf("%d %d", &n, &m);

   vector<int> t(n);

   for(i=0; i<n; i++){

    scanf("%d", &t[i]);

    rt+=t[i];

    if(t[i]>max) max=t[i];

   }

   while(lt<=rt){

    mid=(lt+rt)/2;

    for(i=0; i<n; i++){

    sum+=t[i];

    if(sum>mid){

    sum=0;

    cnt++;

    i--;

    }

    }

    if(mid>=max && cnt==m){

    ans=mid;

    rt=mid-1;

}else{

    lt=mid+1;

}

   }

   printf("%d\n", ans);

   

   

   return 0;

}

2. while(lt<=rt)라는 조건을 이용하여 반복문을 실행하는데, 여기서 lt<=rt 조건을 어떻게 벗어나서 반복이 종료되는 것인지 궁금하여 질문드립니다.