[참고자료]이분탐색을 활용한 UpperBound& LowerBound

1. UpperBound(랜선자르기, 예산)

💡 보통 문제에 “최댓값”을 구한다는 표시가 나타나 있음

EX) 관련 문제 예시

• 예산

2512번: 예산

 

• 랜선 자르기

 

1654번: 랜선 자르기

이럴 경우 upper bound를 구한뒤 -1을 한 값이 최댓값을 구하는 방법임을 기억!

 

upper bound 기억해야 할 것

1. max값에는+1을 해주어야 함
   • upper bound는 값-1을 해주는 방법으로 최댓을 계산한다.
   • 따라서 예를들어 [1 2 3 4 5] 가 있을 때, 답이 5일 경우에는 while문을 전부 돌고 나오는 값이 6을 가리켜야 -1 해서 5가 나올 수 있다.
2. min값은 답이 될 수 있는 가장 작은 값이 오면 됨
   • 0,1 등 문제를 잘 읽고 답이 될 수 있는 가장 작은 값을 넣어주면 됨.
   • 그런데 0이 들어갈경우 divisionByZero 런타임 에러가 날 수 있기 때문에 s는 보통 1 이상으로 책정
   • 0일 경우가 필요하다면 따로 예외처리를 해두는것을 추천
3. if문에서 비교한 값이 구하는 값의 조건에 부합할 때
   • → mid값을 범위에 포함시키지 않는다
4. if문에서 비교한 값이 구하는 값의 조건에 부합하지 않을떄
   • →mid값을 범위에 포함시킨다

 💡 이유는 upperbound는 결국 조건에 부합하는 값들 중 최댓값보다 하나 더 큰값을 구하는 것임. 따라서 조건에 부합할 경우 최종적으로 s~e구간 사이에 존재하면 안되므로 s=mid+1 을통해 mid를 범위에서 제외시켜야한다

예시 코드

1. 랜선 자르기

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

    int k,n,val;
    cin>>k>>n;
    vector<int> v;

    for (int i = 0; i < k; ++i) {
        cin>>val;
        v.push_back(val);
    }

    sort(v.begin(),v.end());
    int index=k-1;
    long long int cnt=0;
    long long int s=1,e=v[index];
    e++;//max값 1 늘려주기
    long long int len=(s+e)/2;
    while(s<e){
        cnt=0;
        for (int i = 0; i < k; ++i) {
            cnt+=v[i]/len;
        }
        if(cnt>=n){//자른 랜선의 개수가 필요한 랜선의 개수보다 같거나 많음=len(mid)값이 조건에 부합함
            s=len+1; //len 값을 범위에서 제외함
            len=(s+e)/2;
        }
        else {//자른 랜선의 개수가 필요한 랜선의 개수보다 적음=len(mid)값이 조건에 부합하지 않음
            e=len; //len 값을 범위에 포함
            len=(s+e)/2;
        }
    }
    cout<<s-1;

}

2. 예산

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

    int m,n,val;
    cin>>n;
    vector<int> v;

    for (int i = 0; i < n; ++i) {
        cin>>val;
        v.push_back(val);
    }
    cin>>m;
    sort(v.begin(), v.end());
    long long int len=v[0];
    long long int sum=0;
    long long int s=1, e=v[n-1];
    e++; //max값 1 늘려주기
    while(s<e){
        sum=0;
        for (int i = 0; i < n; ++i) {
            if(v[i]>len){
                sum+=len;
            }
            else{
                sum+=v[i];
            }
        }
        if(sum<=m){//책정한 예산이 조건에 부합함
            s=len+1; //len(mid)값을 범위에서 제외
            len=(s+e)/2;
        }
        else{//책정한 예산이 조건에 부합하지 않음
            e=len; //범위에 포함
            len=(s+e)/2;
        }
    }
    cout<<s-1;

}

 

---

 

2. LowerBound(게임)

💡 보통 문제에 “최솟값”을 구한다는 표시가 나타나 있음

 

EX) 관련 문제 예시

• 게임

 

1072번: 게임

이럴 경우 lower bound를 구하는 것이 최솟값을 구하는 방법임을 기억!

lower bound 기억해야 할 것

1. max값에는 답이 될 수 있는 가장 큰 값이 오면 됨
2. min값은 답이 될 수 있는 가장 작은 값이 오면 됨
   • 그런데 0이 들어갈경우 divisionByZero 런타임 에러가 나기때문에 s는 보통 1 이상으로 책정
   • 0일 경우가 필요하다면 따로 예외처리를 해두는것을 추천
3. if문에서 비교한 값이 구하는 값의 조건에 부합할 때
   • → mid값을 범위에 포함시킨다
4. if문에서 비교한 값이 구하는 값의 조건에 부합하지 않을떄
   • →mid값을 범위에 포함시키지 않는다

💡 이유는 lowerbound는 결국 조건에 부합하는 값들 중 최솟값을 구하는 것임. 따라서 조건에 부합하지 않는다면 범위에서 제외시켜야함

예시 코드

1. 게임

#include <iostream>
using namespace std;

int main() {
	double x,y,z;
	cin >> x >> y;
	int z_score = y*100/x;
	int z_int;
	if (z_score >= 99) {
		cout << -1;
		return 0;
}
	int add,s,m,e;
	s = 1;
	e = x; //max값 1 안늘려줘도 됨
	m = (s + e) / 2;
	while (s<e) {
		z_int=(y + m)*100 / (x+m);
		if (z_int!=z_score) {//조건에 부합한다면
			e = m; //범위에 포함시킴
		}
		else { //조건에 부합하지 않는다면
			s = m + 1; //범위에서 제외함
		}

		m = (s + e) / 2;
	}
	cout << e;
	return 0;
}