[백준] 1654번: 랜선 자르기 [C++]

알고리즘 분류: 이분 탐색, 매개 변수 탐색

문제 링크: https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

 

 

【 풀이 】

 

2805번과 비슷하게 구할 수 있는 문제이다.

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

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

2805번과 다른 점은 단 하나다. 

total(결괏값들을 더하는 변수)에 배열 요소에서 mid를 뺀 값이 아닌, mid를 나눈 값을 저장해야 한다는 것이다.

그리고 이 문제에서는 배열 요소들이 커지기 때문에 자료형을 모두 long long으로 선언해 주는 것이 좋다.

 

 

【 코드 】

 

#include<iostream>
#include<vector>
using namespace std;

vector<long long int>LAN;
int main(void)
{
	long long int sum = 0;
	int m, n;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		long long int num;
		cin >> num;
		LAN.push_back(num);
	}

	for (int i = 0; i < n; i++)
		sum += LAN[i];

	long long int start = 1;
	long long int end = sum;
	long long int height=0;
	while (start <= end)
	{
		long long int total = 0;
		long long int mid = (start + end) / 2;
		for (int i = 0; i < LAN.size(); i++)
				total += LAN[i] / mid;
		if (total < m)
			end = mid - 1;
		else
		{
			height = mid;
			start = mid + 1;
		}
	}
	cout << height;
	return 0;
}