이분탐색(4) - 과자 나눠주기, 나무 자르기, 공유기 설치, 예산, 휴게소 세우기

 

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

16401번: 과자 나눠주기

매개 변수 탐색을 이용한 문제이다. 0을 출력하는 것은 예외처리를 하는 것이 아니라 st en 범위 설정으로 해결할 수 있다.

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

int m,n;
int a[1000003];

bool solve(ll x){
    ll cur=0;
    for(int i=0;i<n;i++) cur+=(int)(a[i]/x);
    return cur>=m;
}

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin>>m>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    ll st=0; ll en=1000000000;
    while(st<en){
        ll mid=(st+en+1)/2;
        if(solve(mid)) st=mid;
        else en=mid-1;
    }
    cout<<st;
    return 0;
}

---

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

2805번: 나무 자르기

앞과 거의 같은 문제이다. 풀면서 실수했던 점은 절단기 높이를 0으로도 설정할 수 있었다는 점이었다...

또 답지를 참고했는데 en을 max element를 활용해 범위를 대폭 줄일 수 있었다.

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

int m,n;
int a[1000003];

bool solve(ll x){
    ll cur=0;
    for(int i=0;i<n;i++){
        if(a[i]-x>0) cur+=(a[i]-x);
    }
    return cur>=m;
}

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>a[i];
    ll st=0; ll en=*max_element(a,a+n);
    while(st<en){
        ll mid=(st+en+1)/2;
        if(solve(mid)) st=mid;
        else en=mid-1;
    }
    cout<<st;
    return 0;
}

---

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

2110번: 공유기 설치

while과 lower_bound를 사용해 다음 번 인덱스로 넘어가게 구현한 게 신기했다. 

//https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x13/solutions/2110.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,c; //집의 개수, 공유기의 개수
int a[200003];

bool solve(ll x){
    int cnt=0,idx=0;
    while(idx<n){ //idx가 n을 넘길 수 없음
        idx=lower_bound(a+idx,a+n,a[idx]+x)-a;
        //cout<<a[idx]<<' ';
        cnt++;
    }
    //cout<<'\n';
    return cnt>=c;
}

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>c;
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    ll st=1; ll en=1000000000;
    while(st<en){
        ll mid=(st+en+1)/2;
        if(solve(mid)) st=mid; 
        else en=mid-1;
    }
    cout<<st;
    return 0;
}

---

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

2512번: 예산

이제 실버~골하위는 쉽게 자력솔을 해낼 수 있다. en에 max_element를 사용해야 제대로 된 결과가 나온다. 앞으로도 웬만하면 max_element를 사용하는게 좋을 것 같다.

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

int n,m;
int a[200003];

bool solve(ll x){
    ll cur=0;
    for(int i=0;i<n;i++){
        if(a[i]<=x) cur+=a[i];
        else cur+=x;
    }
    return cur<=m;
}

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    cin>>m;
    sort(a,a+n);
    ll st=1; ll en=*max_element(a,a+n);
    while(st<en){
        ll mid=(st+en+1)/2;
        if(solve(mid)) st=mid; 
        else en=mid-1;
    }
    cout<<st;
    return 0;
}

---

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

1477번: 휴게소 세우기

이분탐색에서 범위 세우는게 너무 까다롭다. 몇 문제 안풀어봐서 아직까진 어떻게 해야 할지 잘 모르겠다.

이 문제도 더 공부하고 다시 풀어봐야 할 것 같다.

//https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x13/solutions/1477.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,m,l;
int a[53];

bool solve(int x){
    int must_cnt=0; 
    int sub=0; //뺄 값
    for(int i=0;i<=n;i++){
        int dist=a[i]-sub;
        if(dist>=x){
            if(dist%x!=0) must_cnt+=(dist / x);
            else must_cnt+=(dist / x - 1);
        }
        sub=a[i]; //뺄 값을 갱신
    }
    return must_cnt>m;
}

int main(void){
    cin.tie(0); ios::sync_with_stdio(0);
    cin>>n>>m>>l;
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    a[n]=l;
    int st=1; int en=l;
    while(st<en){
        int mid=(st+en)/2;
        if(solve(mid)) st=mid+1;
        else en=mid;
    }
    cout<<st;
    return 0;
}