작은시작

문제

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

풀이

문제를 보면 나무의 높이, 절단기 높이 등 int의 숫자 범위를 넘는다.  또한 적어도+최댓값 등을 찾을 때는 이분 탐색을 의심해보자

두 가지 실수하지 않도록 조심하자

1. long long 변수형이 어디 어디에 필요한지

2. 나무절단시 if문을 통해 음수 걸러주기 

코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int H;
int N;
long long M; //숫자가 너무 큰 탐색 -> 이분탐색 의심
vector<long long> arr;
long long answer;
int main() {
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		long long abc;
		cin >> abc;
		arr.push_back(abc);
	}

	sort(arr.begin(), arr.end(),greater<>());

	//이분탐색
	long long low = 0;
	long long high = arr[0];
	while (low <= high) {
		long long middle = (low + high) / 2;
		
		long long sum = 0;
		for (int i = 0; i < N; i++) {
			if(arr[i]-middle>0) sum += arr[i] - middle;

		}
		if (sum >=M) {
			low = middle + 1;
			answer = middle;
		}
		else { // 나무 부족, 절단기 높이 줄임
			high = middle - 1;

		}



	}
	cout << answer;





	return 0;
}

문제

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

풀이

이분 탐색을 바로 생각해내야만 하는 문제였다. 이분 탐색 기본 유형

조건을 만족하면서(Possible) 조건 내 최댓값을 이분 탐색을 통해 찾아내야 한다.

이분 탐색시 랜선길이 개수를 보면 2^32-1 이다. 이를 전부 탐색하려면 이분탐색 방법뿐만 아니라 자료형 또한

long long 이 필요함을 잊지 말자. 

코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int N; //필요한 랜선 개수
int K; //보유한 랜선 개수
vector<long long> kk; //랜선길이개수가 2^32-1 보다 작거나 같은 자연수이므로 longlong 선언
bool Possible(int mid) {
	long long cnt = 0;
	for (int i = 0; i < K; i++) {

		cnt += kk[i] / mid;

	}
	if (cnt >= N) {
    
		return true;
	}
	return false;

}
int main() {
	cin >> K >> N;
	//항상 K <= N

	for (int i = 0; i < K; i++) {
		int a; 
		cin >> a;
		kk.push_back(a);
	}

	//이분탐색
	long long low = 1;
	long long result = 0;
	//high찾기
	long long high = 0;
	for (int i = 0; i < K; i++) {
		
		high = max(kk[i], high);

	}

	while (low <= high) {
		long long mid = (high + low) / 2;
		if (Possible(mid)) {

			if (result < mid)  result = mid;

			low = mid + 1;
		
		}
		else {
			high = mid - 1;
		}

	}

	cout << result;

	return 0; 
}

https://programmers.co.kr/learn/courses/30/lessons/43238

코드 설명 

시간 이라는 개념을 이분탐색으로 찾아야 한다는게 포인트이다.

최소값은 1분 ~ 최대값은 times가 가진 최대 시간 * n(사람수) 이다.

그 후, mid시간 동안 몇명을 검사 할수 있는지 cnt를 통해 구한다. ( 구하는 법은 시간/times[i])

또한 최대값을 설정할때 long long 설정에 유의하자!

long long endd=n*(long long)times[k-1];

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    //입국심사 사람 1,000,000,000 => longlong 이분탐색 생각!
    sort(times.begin(),times.end());
    long long k=times.size();
    long long startt=1;
    long long endd=n*(long long)times[k-1];
    long long cnt=0;
    
    
    while(startt <= endd){
    long long midd=(startt+endd)/2;
        cnt=0;
     for(int i=0;i<k;i++){
        cnt += midd/times[i]; //시간당 심사인원한명이 심사할수 있는 인원수 합
    }
       
        if(cnt<n){  // 불가능
            startt = midd+1;    
        }
        else{ //가능 
            //최소시간 구하기
            answer=midd;
            endd=midd-1;
        }
        
    
    }
    
    
    
    return answer;
}