백준 1654 : 랜선 자르기 (이진탐색 알고리즘)

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

1. 접근

• 랜선의 길이는 반드시 1~(랜선 중 최대 길이) 의 값을 갖는다
• 랜선의 길이는 2^31-1 이므로, unsigned int 를 사용해야 한다
• 모든 길이로 잘라볼 수 있으나 시간초과가 발생한다.
  => 빠른 길이 탐색을 위해, 가장 빠른 이진탐색을 사용해야 한다.

• start,end,mid 값을 이용해 이진탐색을 진행한다.
• 어떤 길이가 최대 길이인지를 확인하기 위해 이진탐색을 진행하므로, 한번 실행했을 때의 tem 값이 n보다 큰지, 작은지에 따라 start와 end값을 조정한다

2. 나의 풀이

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 10001
using namespace std;

int main() {
	int k, n;
	unsigned int maxval = 0;
	unsigned int arr[MAX];
	cin >> k >> n;

	for (int i = 0; i < k; i++) {
		cin >> arr[i];
		maxval =max(arr[i], maxval);
	}

	unsigned int start=1, end= maxval, mid;
	unsigned int ret = 1;

	while (start <= end) {
		mid = (start + end) / 2;

		unsigned int tem = 0;
		for (int i = 0; i < k; i++) {
			tem += arr[i] / mid;
		}

		if (tem >= n) {
			start = mid + 1;
			ret = max(ret, mid);
		}
		else {
			end = mid - 1;
		}
	}

	cout << ret;
	return 0;
}

3. 참고

https://yongmemo.tistory.com/21