(c++)백준 1654번: 랜선 자르기

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

1654번: 랜선 자르기

[풀이]

이분탐색으로 푸는 문제였다.

처음에 재귀로 풀려고 했지만 시간초과에 계속 틀렸다고 떠서 반복문으로 바꿨다.

초기 low는 어찌 됐든 1이상의 길이로 자를 수 있으니까 1, high는 입력되는 전선들 중 가장 긴 전선의 길이로 설정했다.

그리고 이분탐색으로 low부터 high까지 길이중 K개 전선들을 N개 이상으로 나눌 수 있는 가장 긴 길이를 구했다.

 

#include <iostream>
#include <algorithm>//max
#include <cstdio>//scanf,printf
using namespace std;

int K, N;
long long Line[10001];

bool Separate(long long len) {
	int lines = 0;
	for (int i = 0; i < K; i++) {
		lines += Line[i] / len;
	}

	//N개 이상 만들 수 있으면
	if (lines >= N)
		return true;
	return false;
}

void solution() {
	cin >> K >> N;
	
	long long high = 0;
	for (int i = 0; i < K; i++) {
		cin >> Line[i];
		//가장 긴 전선 길이 저장
		high = max(high, Line[i]);
	}

	long long MaxLen = 0;//N개 만들 수 있는 랜선 최대 길이
	long long low = 1;
	//1센티미터 ~ High센티미터 사이에서 N개로 나눌 수 있는 가장 큰 수 구하기
	while (low <= high) {
		long long mid = (low + high) / 2;

		if (Separate(mid)) {
			MaxLen = max(MaxLen, mid);
			low = mid + 1;
		}
		else {
			high = mid - 1;
		}
	}

	cout << MaxLen << endl;
}

int main() {
	solution();
	return 0;
}