이분 탐색

Silver 2805

첫시도

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

vector<int> v;
int N, M;
int tree[1000000];

int cuttingTree(vector<int>& v, int target, int start, int end) {
	while (start <= end) {
		int have = 0;
		int mid = (start + end) / 2;
		for (int i = 0; i < N; i++) {
			if (v[i] > mid) {
				have = have + v[i] - mid;
			}
		}
		if (have > target) { start = mid + 1; }
		else if (have < target) { end = mid - 1; }
		else { return mid; }
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> tree[i];
		v.push_back(tree[i]);
	}
	sort(v.begin(), v.end());
	int high = cuttingTree(v, M, v[0], v[N - 1]);
	cout << high;

	return 0;
}

시간초과!
예제 답은 나오는데 시간초과 이유를 모르겠다
for문의 N의 최댓값 1,000,000과 O(N)
while문의 최댓값 2,000,000,000 O(logN)
O(NlogN)로 1,000,000 X log(2,000,000,000) =30,000,000 < 100,000,000 이여서 문제에 대한 시간초과는 아닌 것 같고
만약에 아니면 while문 무한루프에 빠졌다는건데 반례를 찾아봐야겠다.

두번째시도

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

vector<int> v;
int N, M;
int tree[1000000];

int cuttingTree(vector<int>& v, int target, int start, int end) {
	int max = 0;
	while (start <= end) {
		long long have = 0;
		int mid = (start + end) / 2;
		for (int i = 0; i < N; i++) {
			if (v[i] > mid) {
				have = have + v[i] - mid;
			}
		}
		if (have > target) { 
			start = mid + 1; 
			if (mid > max) { max = mid; }
		}
		else if (have < target) { end = mid - 1; }
		else { return mid; }
	}
	return max;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> tree[i];
		v.push_back(tree[i]);
	}
	sort(v.begin(), v.end());
	cout<< cuttingTree(v, M, 0, 2000000000);

	return 0;
}

생각보다 놓친 점이 아주 많았다

1. cout<< cuttingTree(v, M, 0, 2000000000);
   start를 0으로 설정해주어야

   입력 값
   3 10
   3 1 1
   출력값
   0

위와 같이 이분탐색에서 start와 end값은 겹치면도 안될뿐더러 0과 같은 남는부분도 없어야 한다. (범위를 처음부터 끝까지 정해줬었어야한다.)

2. return max;
   첫 시도에서는 잘려진 나무 have와 target이 딱 같은 경우에서만 올바른 정답이 나왔지만 딱 떨어지지 않을 때도 정확한 답이 나와야한다. 문제에서는 적어도 M미터의 나무를 가져가기 위하여 절단기의 최댓값을 구하는 문제이다. 절단기의 높이가 높아질수록 가져갈 수 있는 나무의 길이는 적어지기 때문에
   잘려진 나무의 길이 have가 target보다 클 때 mid의 최댓값을 계속 초기화하며

if (have > target) { 
			start = mid + 1; 
			if (mid > max) { max = mid; }
} 

while문의 조건을 만족하지 않을 때 함수는 return max를 해야한다.

3. long long have = 0;
   have 같은 경우 v벡터의 값을 계속해서 더해주므로 int의 최댓값인 2,147,483,647(대략 20억)을 넘을 가능성이 있으므로 범위가 더 큰 long long 데이터 타입을 이용하여 범위 설정을 해주었다.

Silver 1654

첫시도

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


int K, N;
long long arr[10000];
int main() {
	long long max=0;
	long long ans = 0;
	long long start = 1;
	long long end = INT_MAX;
	long long EA = 0;
	cin >> K >> N;
	for (int i = 0; i < K; i++) {
		cin >> arr[i];
	}
	while (start <= end) {
		EA = 0;
		long long mid = (start + end) / 2;
		for (int i = 0; i < K; i++) {
			EA = EA + arr[i] / mid;
		}
		if (EA == N) { ans = mid; break; }
		else if (EA > N) {
			start = mid + 1;
			if (mid > max) { ans = mid; }
		}
		else  {
			end = mid - 1;
		}
	}
	cout << ans;


	return 0;
}

예제 출력값이 200이 나와야 하는데 192가 나온다

두번째시도

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


int K, N;
long long arr[10000];
int main() {
	long long max=0;
	long long ans = 0;
	long long start = 1;
	long long end = 2147483647;
	long long EA = 0;
	cin >> K >> N;
	for (int i = 0; i < K; i++) {
		cin >> arr[i];
	}
	while (start <= end) {
		EA = 0;
		long long mid = (start + end) / 2;
		for (int i = 0; i < K; i++) {
			EA = EA + arr[i] / mid;
		}
		if (EA >= N) {
			start = mid + 1;
			if (mid > max) { ans = mid; }
		}
		else  {
			end = mid - 1;
		}
	}
	cout << ans;


	return 0;
}

첫시도에서는 EA가 192가 될 때 EA = 4+3+2+2 = 11이 되면서 while문이 break;되는데 EA가 11이여도 더 큰 길이로 EA를 11로 만들 수 있는지 확인을 해봐야한다!
->그러므로 EA = K인 경우에도 start = mid + 1을 통해 길이가 더 큰 쪽으로 탐색을 시작하여 길이의 최댓값을 찾을 수 있습니다.