[백준 C++] 2805번: 나무자르기

2805번: 나무 자르기

1. 시간제한에서 엄청 걸림-> 이분탐색으로 해결

2. 처음엔 m==sum이거나 i==start 면 루프를 빠져나가는 방식으로 해결함-> WA발생

3. 자료형 확인 제대로 안해서 long int형을 사용하지 않아 문제 발생

 이후 WA반복되다가

6 12
19 9 18 20 17 8

답: 15

1 1000000000
1000000000

답: 0

 

해당 테스트케이스에서 틀린 답 확인

 

 

 

벡터를 사용할까 배열을 사용할까 고민하다 접근이 많은 문제라 배열 사용 결정

 

소스코드

#include<iostream>
using namespace std;
long long int tree[1000000];
int main() {
	int n;
	long long int m, max = 0;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> tree[i];
		if (max < tree[i]) {
			max = tree[i];
		}
	}

	long long int start = 0, end = max;
	long long int mid = start + (end - start) / 2;
	long long int i,cut;
	while (start<=end) {
		i = mid;
		long long int sum = 0;
		for (int j = 0; j < n; j++) {
			if (i >= tree[j])
				continue;
			sum += tree[j] - i;
		}
		if (sum == m) {
			cut = i;
			break;
		}
		else if (sum > m) {
			start = mid + 1;
			cut = i;
			}
		else {
			end = mid - 1;

		}
		mid = start + (end - start) / 2;
	}

	cout << cut;
	return 0;
}