[C++] 백준(BOJ) 1654 - 랜선 자르기

- 문제

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

1654번: 랜선 자르기

- 문제 분석

조건

1) K(기존 랜선의 개수) : 1 ~ 10000

2) N(필요 랜선의 개수) : 1 ~ 1,000,000

3) K ≤ N

4) 랜선의 길이 : 1 ~ 2³¹-1 (여러 랜선을 더하고 빼는 경우 int 범위 초과 => long long 사용)

 

문제의 요구사항대로 최대 길이의 랜선을 N개로 나누기 위해서는 기존 K개의 랜선을 나누고 난 나머지가 최소가 돼야 한다.

다시 말해 K개의 랜선을 모두 이어 붙인 뒤 이를 N으로 나눈 결과가 가장 이상적인 최댓값이 된다.

 

가능한 길이의 최대값을 구하는 과정

하지만, 실제로는 각각의 랜선을 나눠야 하기 때문에 실제로 버리는 부분이 더 많을 수도 있다. 따라서 구하고자 하는 값은 1~maxLen 사이의 값들 중 조건을 만족하는 수들의 최댓값이다.

 

범위가 정해진 정렬된 값들 중 조건을 만족하는 수를 구하는 알고리즘 => 이분 탐색(Binary Search)

 

- 풀이

이번 이분 탐색의 특징은 조건을 만족하는 수를 단순히 선택하는 것이 아니라 특정 조건을 만족하는 수 중 최댓값을 찾는 것이다. 

때문에 이를 고려하여 이분 탐색을 수행해야 한다.

만약 위 처럼 mid값이 조건을 만족하지만, 최댓값이 아닐 경우 계속 수를 찾아야 한다.

따라서 분기 조건을 다음과 같이 설정했다.

1) mid 값이 조건을 만족하면 : Left = mid + 1

2) mid 값이 조건을 만족하지 않으면 : right = mid

 

이 조건대로 탐색 완료 시점의 상황에서 발생할 수 있는 경우의 수를 따져보면 다음과 같다.

• Left에 범위의 최댓값이 걸치는 경우

• mid에 범위의 최댓값이 걸치는 경우 

• Right에 범위의 최댓값이 걸치는 경우

위의 결과를 통해 Left와 Right가 같아지는 순간에서 mid의 조건을 만족하는 지의 여부에 따라 값을 정하면 최댓값을 찾을 수 있다.

 

- 코드

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
typedef long long ll;

ll k, n;
ll maxLen = 0;
vector<ll> lines;

void init() {
	// 입력 및 변수 초기화
	cin >> k >> n;
	for (int i = 0; i < k; i++) {
		ll a; cin >> a;
		lines.push_back(a);
		maxLen += a;
	}

	maxLen /= n;	// 범위의 최대값 설정
}
bool isCorrect(ll len) {
	// 해당 길이로 잘랐을 때 몇개를 만들지 계산(조건 확인)
	ll cnt = 0;
	for (ll& i : lines) {
		cnt += (i / len);
	}
	return n <= cnt;
}
ll solve() {
	// 이분탐색
	ll left = 1;
	ll right = maxLen;

	while (left < right) {
		ll mid = (left + right) / 2;

		if (isCorrect(mid)) {
			left = mid + 1;
		}
		else {
			right = mid;
		}
	}
	return isCorrect(right) ? right : right - 1;
}

int main() {
	fastio;

	init();
	cout << solve();
}