[백준/BOJ] 1654 - 랜선 자르기 (c++) (이분탐색)

1. 문제

 

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

---

2. 풀이

이 문제는 답을 이분탐색을 이용하여 구하는 문제이다.

 

답은 1부터 2^31 - 1사이에 존재한다.

 

따라서 이 사이의 값 중 답이 되는 값중에 최댓값을 구하기 위해 이분탐색을 사용하면 된다.

 

또 다른 주의할점은

 

이분탐색을 할때 mid값을 구할때 m = (l + r) / 2인데

 

l이 1이고, r이 2^31 - 1이어서 더하게 되면 int형 사이즈를 초과하기때문에 

 

l, r, m을 long long 형으로 변환시켜줘야한다.

---

3. 소스코드

#include <iostream>
#include <climits>

using namespace std;

int n, k, arr[10000];

bool makeN(int m) {
	int line = 0;

	for (int i = 0; i < k; i++) line += arr[i] / m;

	if (line >= n) return true;
	else return false;
}

int main() {
	ios::sync_with_stdio(0);
	cin >> k >> n;
	for (int i = 0; i < k; i++) cin >> arr[i];

	long long l = 1, r = INT_MAX, m;
	while (l <= r) {
		m = (l + r) / 2;
		if (makeN(m)) l = m + 1;
		else r = m - 1;
	}
	cout << r;
}

---

4. 참고

 

---

질문, 고칠점 등 댓글 언제나 환영입니다.