[백준][이진 탐색] 1654 랜선 자르기 c++구현 및 설명

목차

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

1654번: 랜선 자르기

문제

 

문제 구현 방향

범위가 아주 크기 때문에 이진 탐색을 통해 해결하지 않으면 시간 초과가 나는 문제이다.

또한 정수의 범위가 매우 크기 때문에 long long int를 쓰고자 했다.

아래 기본 코드에서 약간 변형하고 아이디어를 더하면 풀리는 문제이다.

 

 

이진탐색 기본 구현 코드

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

//이진 탐색 함수
int Binarysearch(vector<int> &arr, int n, int target) {
	int low = 0, high = n - 1;

	while (low <= high) {
		int mid = (high + low) / 2;
		int mid_value = arr[mid];
		if (mid_value == target)  //중간 값이 목표값이면 반환
			return mid;
		else if (mid_value > target)  // 중간 값이 더 크면 상한을 줄임
			high = mid - 1;
		else    //중간 값이 더 작으면 하한을 올림
			low = mid + 1;
	}
	return -1;   //못찾으면 -1 반환
	
	
}

// 배열 출력 함수
void printArray(vector <int>&arr, int size) {
	for (int i = 0; i < size; ++i)
		cout << arr[i] << " ";
	cout << endl;
}

int main() {
	vector <int>arr = { 3, 4, 2, 1, 5, 10, 24, 50, 73 };
	sort(arr.begin(), arr.end());
	printArray(arr, 9);
	cout << Binarysearch(arr, 9, 10);

}

 

 

 

코드구현

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
int K, N;
vector <long long int>Lan;


//선택 정렬 함수
void Binarysearch(int start, int target) {
	long long int low = 1, high = start, i, mid_value, mid;  //하한은 정수범위의 1
	while (low <= high) {
		mid = (high + low) / 2;
		mid_value = 0;
		for (i = 0; i < K; i++) {
			mid_value += Lan[i] / mid;
		}

		if (mid_value < target)   //목표수보다 작을 때 상한을 줄여준다.
			high = mid - 1;
		else   //목표수보다 크거나 같은 때 하한을 늘려준다. (이 조건 떄문에 아래 조건이 필요)
			low = mid + 1;
	}

	if (mid_value < target)  //목표수보다 적제 종료될때
		cout << mid - 1;
	else    //목표수보다 크거나 같게 종료될때
		cout << mid;
}

int main() {
	long long int i, j, cm, max_cm;

	cin >> K >> N;
	for (i = 0; i < K; i++) {
		cin >> cm;
		Lan.push_back(cm);
	}
	auto iter = max_element(Lan.begin(), Lan.end());   
	max_cm = *iter;    //최대값을 상한으로 설정
	
	 Binarysearch(max_cm, N);


}