[Algorithm] 6주차 스터디 - 이분탐색(백준 18113, 2805, 1920, 2110)

A - 18113 그르다 김가놈

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

18113번: 그르다 김가놈

코드 

#include <iostream>
#include <vector>
 
using namespace std;

vector<int> v;
 
int main() {
	cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    
    int n, k, m, gb;
    int l = 1, r = 1000000000, mid, count, p = -1;
    cin >> n >> k >> m;
    
    for (int i = 0; i < n; i++) {
        cin >> gb;
        if (gb > 2 * k)
            v.push_back(gb - 2 * k);
        if (2 * k > gb && gb > k)
            v.push_back(gb - k);
    }
    while (l <= r) {
        mid = (l + r) / 2;
        count = 0;
        for (int gb:v)
            count += gb / mid;
        if (count >= m) {
            p = mid;
            l = mid + 1;
        } else
            r = mid - 1;
    }
    cout << p << '\n';
    return 0;
}

문제 풀이 

김밥의 길이를 입력받은 뒤에 길이가 2K보다 긴 경우에는 양쪽을 자르고 벡터에 넣고, 2k보다 작고 k보다 긴 경우에는 한 쪽만 자르고 벡터에 넣는다. 
이후에 이분탐색 알고리즘을 쓴다. mid에서 만들 수 있는 김밥의 개수를 세고 출력한다. left 인덱스가 right 인덱스보다 작은 동안 과정을 반복한다. 

B - 2805 나무 자르기 

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

2805번: 나무 자르기

코드 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long n, m, answer = 0;

vector<long long> v;

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

	cin >> n >> m;

	for (long long i = 0; i < n; i++) {
		long long tmp;
		cin >> tmp;
		v.push_back(tmp);
	}

	sort(v.begin(), v.end());

	long long l = 0;
	long long r = v[n - 1];

	while (l <= r) {

		long long sum = 0;
		long long mid = (l + r) / 2;
		
		for (int i = 0; i < n; i++) {
			if ((v[i] - mid) > 0)
				sum += (v[i] - mid);
		}

		if (sum < m) {
			r = mid - 1;
		}
		else if (sum >= m) {
			if (answer < mid)
				answer = mid;
			l = mid + 1;
		}
	}
	cout << answer << endl;
	return 0;
}

문제 풀이 

나무의 길이들을 다 입력받고 배열에 저장해서 정렬한다. 이후에 중간값을 택하고 나무 길이에서 중간 길이를 뺀 값이 0보다 크면 다 더해준다. 다 더한 값이 m보다 작으면 오른 쪽 끝 값을 조정한 뒤에 다시 이분탐색을 진행한다. m보다 큰 경우 우리가 찾고자 하는 답이 중간보다 작으면 mid를 답으로 해준다. 답을 찾게 되면 출력해준다. 

C - 1920 수 찾기 

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

1920번: 수 찾기

코드 

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int arr[100001];
int arr2[100001];
 
void binarySearch(const int & n, const int & k) {
    int first = 0;
    int last = n - 1;
    int mid = 1;
    while (first <= last) {
        mid = (first + last) / 2;
        if (arr[mid] == k) {
            cout << "1\n";
            return;
        }
        else {
            if (arr[mid] > k)
                last = mid - 1;
            else
                first = mid + 1;
        }
    }
    cout << "0\n";
    return;
}
 
int main() {
	cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(0);
 
    int n, m;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> arr2[i];
    }
 
    sort(arr, arr + n);
    for (int i = 0; i < m; i++) {
        binarySearch(n, arr2[i]);
    }
 
}

문제 풀이 

이 문제는 그냥 이분탐색을 사용해서 풀면 되는 문제이다. 먼저 두 개의 배열을 입력받은 다음에 정렬해준다. 정렬한 뒤에 배열에 숫자가 있는지 없는지 이분탐색을 하며 찾아내면 되는 심플한 문제이다. 

D - 2110 공유기 설치 

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

2110번: 공유기 설치

코드 

#include <iostream> 
#include <vector> 
#include <algorithm> 

using namespace std; 
int n ,c; 
vector<int> houses; 

int main() { 
	cin.tie(0); cout.tie(0); 
	ios::sync_with_stdio(false); 
    
    cin >> n >> c;
    for (int i = 0; i < n; i++) { 
    	int temp; 
    	cin >> temp; 
        houses.push_back(temp); 
    } 
    
    sort(houses.begin(), houses.end()); 
    
    int start = 1; 
    int end = houses[n-1] - houses[0];
    int result = 0;  
    
    while (start <= end) { 
    	int mid = (start+end) / 2; 
        int cnt = 1; 
        int prev_house = houses[0]; 
        
        for (int i = 1; i < n; i++) { 
        	if (houses[i] - prev_house >= mid) { 
        		cnt++; 
                prev_house = houses[i]; 
            }
        }  
        if (cnt >= c) { 
            result = max (result, mid); 
            start = mid+1; 
        } 
        else end = mid-1; 
    } 
    cout << result; 
    return 0; 
}

문제 풀이 

 집의 좌표들을 입력받은 뒤에 정렬한다. 이 문제는 좌표들을 이분탐색을 진행하는 것이 아닌 좌표들 사이의 최소거리의 최댓값을 찾기 위해 이분탐색을 사용한다. 최소거리의 범위가 1부터 양 끝 집의 거리 사이에 있으므로 start를 1, end를 houses[n-1] - houses[0]로 두고 이분탐색을 시작한다. 중간값이 최솟값이라고 가정을 하고 이에 필요한 공유기의 수를 cnt로 구한다. 필요한 공유기보다 많은 수가 세어졌을 경우, 최소거리가 더 커져야함으로 start를 mid+1로 둔다. 반대의 경우, 최소거리가 더 작아져야 하기 때문에 end를 mid-1로 두고 다시 이분탐색을 시작한다. start가 end보다 더 커지면 반복문에서 빠져나와 공유기의 개수를 출력한다.