[BOJ] 1654번 랜선 자르기 (C++)

문제 (https://www.acmicpc.net/problem/1654)

1654번: 랜선 자르기

전에 올린 나무 자르기와 비슷한 듯 다른 문제..!

 

나는 end 값을 입력받은 길이 중 가장 큰 값이 아닌 모든 길이의 합을 n으로 나눈 값으로 정했다. 

각 길이를 mid로 나누었을 때 몫의 합이 n보다

- 크거나 같다면? 랜선의 길이를 더 길게 start 이동, 최댓값이라면 답으로 설정

- 작다면? 랜선의 길이를 더 짧게 end 이동

---

[소스코드]

	/* BOJ 1654번: 랜선 자르기
	2021-03-23
	Binary Search */
	#include <iostream>
	#define MAX
	using namespace std;
	int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int k, n;
	long long start = 1, end, mid, sum = 0, total, max = -1;
	cin >> k >> n;
	int length[k];
	for(int i = 0 ; i < k ; i++){
	cin >> length[i];
	sum += length[i];
	}
	end = sum / n;
	while(start <= end){
	total = 0;
	mid = (start + end) / 2;
	for(int i = 0 ; i < k ; i++){
	total += length[i] / mid;
	}
	if(total >= n){
	start = mid + 1;
	if(mid > max) max = mid;
	}
	else{
	end = mid - 1;
	}
	}
	cout << max;
	return 0;
	}

view raw 1654.cpp hosted with ❤ by GitHub

---

2021-03-23

Silver 3

- 이분 탐색

- 매개 변수 탐색