[백준] 1654번 : 랜선 자르기 & 2805번 : 나무 자르기

🔗 문제 링크

https://www.acmicpc.net/problem/1654 (랜선 자르기)
https://www.acmicpc.net/problem/2805 (나무 자르기)

---

✍️ 문제 풀이

해당 두 문제는 같은 파라메트릭 서치 문제로, 일정 조건을 만족하는 값들 중 최대값을 구하는 문제이다. 파라메트릭 서치는 이진 탐색으로 구현할 수 있다.

[랜선 자르기]

1) 가지고 있는 랜선의 개수와 필요한 랜선의 개수를 입력 받아 저장한다.

2) 가지고 있는 랜선들의 길이를 입력 받아 벡터에 저장하고 이를 오름차순으로 정렬한다.

3) 이진 탐색을 이용해 필요 랜선 개수를 만족하는 최대 랜선 길이를 구한다.

• start는 1, end는 (가지고 있는 랜선 중 가장 긴 랜선의 길이)로 초기화 한다.
• end >= start의 조건을 만족하는 동안 아래 과정을 계속해서 반복한다.
  • start와 end의 중간값인 mid를 구한다.
  • 각 랜선의 길이를 mid로 나눈 값을 count에 누적시킨다.
    • 만약 count가 필요 랜선 개수보다 적을 경우
      • 랜선을 너무 크게 자른 것이므로 현재 mid 이상의 값은 탐색할 필요 X
      • 따라서 end = mid - 1로 변경
    • 만약 count가 필요 랜선 개수보다 많거나 같을 경우
      • 랜선을 너무 작게 자른 것이거나 딱 맞게 자른 경우이므로 현재 mid값 미만의 값은 탐색할 필요 X
      • 따라서 start = mid + 1로 변경, answer에 현재 mid값을 저장해둔다.
        (현재 mid값은 정답이 될 가능성 존재)

4) start가 end보다 커져서 위의 반복이 끝나면 answer에 최대값이 저장되고, 이를 반환한다.

[나무 자르기]

1) 나무의 개수와 필요한 나무의 길이를 입력 받아 저장한다.

2) 나무들의 높이를 입력 받아 벡터에 저장하고 이를 오름차순으로 정렬한다.

3) 이진 탐색을 이용해 필요 나무 길이를 만족하는 최대 절단 높이를 구한다.

• start는 0, end는 (가장 긴 나무 길이 - 1)로 초기화 한다.
  • 0으로 설정하면 모든 나무 길이 전체 더한 것,
  • 가장 긴 나무 길이로 설정하면 가져갈 수 있는 나무 없으므로 (가장 긴 나무 길이 - 1)이 최대
• end >= start의 조건을 만족하는 동안 아래 과정을 계속해서 반복한다.
  • start와 end의 중간값인 mid를 구한다.
  • 각 나무의 길이에서 mid를 뺀 값을 sum에 누적시킨다.
    • 만약 sum이 필요 나무 길이보다 작을 경우
      • 나무를 너무 높게 자른 것이므로 현재 mid 이상의 값은 탐색할 필요 X
      • 따라서 end = mid - 1로 변경
    • 만약 sum이 필요 나무 길이보다 크거나 같을 경우
      • 나무를 너무 낮게 자른 것이거나 딱 맞게 자른 경우이므로 현재 mid값 미만의 값은 탐색할 필요 X
      • 따라서 start = mid + 1로 변경, answer에 현재 mid값을 저장해둔다.
        (현재 mid값은 정답이 될 가능성 존재)

4) start가 end보다 커져서 위의 반복이 끝나면 answer에 최대값이 저장되고, 이를 반환한다.

---

🖥️ 풀이 코드

[랜선 자르기]

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

using namespace std;	
vector<long long> lanLines;

long long binarySearch(int having, int need)
{
	long long start = 1, end = lanLines[having - 1], answer = 0;

	while (end >= start)
	{
		long long mid = (start + end) / 2;
		int count = 0;
		for (int j = 0; j < having; j++)
			count += lanLines[j] / mid;

		if (count < need)
			end = mid - 1;
		else
		{
			answer = mid;
			start = mid + 1;
		}
	}
	return answer;
}

int main(void) 
{
	ios::sync_with_stdio(false);
	cin.tie(); cout.tie();

	int k, n;
	cin >> k >> n;

	for (int i = 0; i < k; i++)
	{
		long long lan;
		cin >> lan;
		lanLines.push_back(lan);
	}
	sort(lanLines.begin(), lanLines.end());
	cout << binarySearch(k, n);
	return 0;
}

[나무 자르기]

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

using namespace std;
vector<long long> trees;

long long binarySearch(long long n)
{
	long long start = 0, end = trees[trees.size() - 1] - 1, answer = 0;

	while (end >= start)
	{
		long long sum = 0;
		long long mid = (start + end) / 2;
		for (int i = 0; i < trees.size(); i++)
		{
			if(trees[i] - mid > 0)
				sum += (trees[i] - mid);
		}
			
		if (sum < n)		
			end = mid - 1;
		else				
		{
			answer = mid;
			start = mid + 1;
		}
	}
	return answer;
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(); cout.tie();

	int n;
	long long m;
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		long long height;
		cin >> height;
		trees.push_back(height);
	}
	sort(trees.begin(), trees.end());
	cout << binarySearch(m);
	return 0;
}